这道题看到小伙伴们有用组合做的，那我就来一个DP吧。

状态: F[i] 表示当前枚举下最大位为i的数个数 （F是一个滚动数组，E数组的存在无特殊意义，只是为了求后缀和）

方程: F[i]=sum(F[j]) (i>j && i<2^K && i<2^W)(注意这个W是在不断变小的)

解法：由原题可知，我们可以先把这个大数的前部分分为W/K个数位，由于进制是2^K，于是这里每个数位转化成十进制的取值都是【1，2^K-1】。但又由于W不一定被K整除，所以可能还会多出来一截数位，假设其长度为X(X<W)，而这个数位转化的取值则是【1，2^X-1】。然后我们开始从第一位枚举每个数位，及时将答案保存并清空之前的统计，就可以统计不同长度下合法数的总个数，详细规则看一下题意就明白了，它已经说得很全面了。

此代码已忽略高精度，很短。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int K, W, N;
int F[1200], E[1200];
int main () {
    
    cin >> K >> W;
    N=((1<<K)-1);
    for(int i=1; i<=N; i++) F[i]=1;
    int x, ans=0;
    while(1) {
        W-=K;
        if (W<=0) break;
        if (W>K) x=N;
        else x=(1<<W)-1;
        for(int i=N; i>=1; i--) E[i]=E[i+1]+F[i], F[i]=0;
        for(int i=x; i>=1; i--) F[i]=E[i+1], ans=ans+F[i];
    }
    printf("%d", ans);
    
}  

完全版本。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct BIGINT {
    int len, num[105];  
    void CLEAR () {
        len=1;
        memset(num, 0, sizeof(num));    
    }
    void PRINT () {
        //printf("%d\n", len);
        for(int i=len; i>=1; i--) printf("%d", num[i]);     
    }
    BIGINT () {
        CLEAR();
    }
    BIGINT (int x) {
        CLEAR();    
        while(x) {
            num[len]=x%10;
            x/=10;
            len++;  
        }
        len--;
    }
    BIGINT operator + (BIGINT x) {
        BIGINT a;
        int maxlen=max(len, x.len);
        for(int i=1; i<=maxlen;i++) a.num[i]=num[i]+x.num[i];
        while(a.num[a.len]>=10||a.len<maxlen) {
            a.num[a.len+1]+=a.num[a.len]/10;
            a.num[a.len++]%=10;
        }    
        return a;
    }
    BIGINT operator * (BIGINT x) {
        BIGINT a;
        int maxlen=len+x.len-1;
        for(int i=1; i<=len; i++) 
            for(int j=1; j<=x.len; j++)
                a.num[i+j-1]+=num[i]*x.num[j];
        while(a.num[a.len]>=10||a.len<maxlen) {
            a.num[a.len+1]+=a.num[a.len]/10;
            a.num[a.len++]%=10;
        }    
        return a;
    }
    bool operator == (BIGINT x) {
        if (len!=x.len) return 0;
        for(int i=1; i<=len; i++) 
            if (num[i]!=x.num[i]) return 0;
        return 1;    
    }
    bool operator > (BIGINT x) {
        if (len<x.len) return 0;
        else if (len>x.len) return 1;
        for(int i=len; i>=1; i--) 
            if (num[i]>x.num[i]) return 1;
            else  if (num[i]<x.num[i]) return 0;
        return 0;   
    }
};
int K, W, N;
BIGINT F[1200], E[1200];
int main () {
    
    cin >> K >> W;
    N=((1<<K)-1);
    for(int i=1; i<=N; i++) F[i]=1;
    int x;
    BIGINT ans=0;
    while(1) {
        W-=K;
        if (W<=0) break;
        if (W>K) x=N;
        else x=(1<<W)-1;
        for(int i=N; i>=1; i--) E[i]=E[i+1]+F[i], F[i]=0;
        for(int i=x; i>=1; i--) F[i]=E[i+1], ans=ans+F[i];
    }
    ans.PRINT();
    
}  

###Pascal
作为一只数竞狗，首选方法是搞一搞公式，然后写一个组合数表，高精度加一加就行了。
前面似乎有人给了公式，这里解释一下公式怎么来的。
1. 写成余数式：w=__p__*k+__r__ 这样在2^k进制下，最高位是0..(2^r)-1，后面的p位是0..(2^k)-1。←shl优先级大于+-，其实括号多余的，不过好看。
2. 首位为0时，后面p位相当于从1..(2^k)-1取出p个数字，从1开始是因为右边严格大于左边。
当然这里p换成p-1也可以，空两位；
换成p-2，空三位；
...
换成2，空p-2位，剩下2位，不能更少了╮(╯▽╰)╭
以上：**Sigma[C[2^k-1,i],{i,2,p}]**
3. 首位为1..(2^r)-1时，后面一定是p位，且依次取的是(首位+1)..(2^k)-1
对首位的所有可能求和：**Sigma[C[2^k-1-i,p],{i,1,2^r-1}]**

下面上代码，实际写的时候还有两个要注意的：
1. dp求组合数表的初始化操作
2. 求出来p比2^k还要大时（后面一共只有2^k个数可以取，p不能取更多）要特判

Program VijosP1315;
const s=100000000;
type x=record
l:array[0..25] of longint;
end;
var
w,k,p,r,i:longint;
c:array[0..512,0..512] of x;
c0,ans:x;

procedure print(c:x);
var i:longint;
begin
for i:=1 to 25 do if c.l[i]<>0 then break;
write(c.l[i]);inc(i);
for i:=i to 25 do begin
if c.l[i]<10000000 then write(0);
if c.l[i]<1000000 then write(0);
if c.l[i]<100000 then write(0);
if c.l[i]<10000 then write(0);
if c.l[i]<1000 then write(0);
if c.l[i]<100 then write(0);
if c.l[i]<10 then write(0);
write(c.l[i]);
end;
end;

function add(x1,x2:x):x;
var i:longint;
begin
for i:=1 to 25 do begin
add.l[i]:=(x1.l[i]+x2.l[i]);
end;
for i:=25 downto 1 do begin
add.l[i-1]:=add.l[i-1]+add.l[i] div s;
add.l[i]:=add.l[i] mod s;
end;
end;

procedure init;
var i,j:longint;
begin
for i:=0 to 25 do c0.l[i]:=0;
for i:=0 to 512 do
for j:=0 to 512 do
c[i,j]:=c0;
c[1,1].l[25]:=1;
for i:=1 to 512 do c[i,0]:=c[1,1];
for i:=1 to 512 do begin
for j:=1 to i do begin
if c[i,j].l[25]=0 then c[i,j]:=add(c[i-1,j],c[i-1,j-1]);
end;
end;
end;

begin
init;
readln(k,w);
p:=w div k;
r:=w mod k;
k:=1 shl k;
if p>=k then begin
p:=k;
r:=0;
end;
ans:=c0;
r:=(1 shl r)-1;
for i:=2 to p do ans:=add(ans,c[k-1,i]);
for i:=1 to r do ans:=add(ans,c[k-1-i,p]);
print(ans);
end.
//处女题解多多指教

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct bigint
{
    vector<int> num;
    int operator == (bigint b)
    {
        if (num.size()!=b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
                if (num[i]!=b.num[i])
                    return 0;
            return 1;
        }
    }
    int operator != (bigint b)
    {
        return ((!(*this==b))?1:0);
    }
    int operator < (bigint b)
    {
        if (num.size()<b.num.size())
            return 1;
        else if (num.size()>b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
            {
                if (num[size-1-i]<b.num[size-1-i])
                    return 1;
                else if (num[size-1-i]>b.num[size-1-i])
                    return 0;
            }
            return 0;
        }
    }
    int operator > (bigint b)
    {
        return ((!(*this<b)&&!(*this==b))?1:0);
    }
    int operator <= (bigint b)
    {
        return ((!(*this>b))?1:0);
    }
    int operator >= (bigint b)
    {
        return ((!(*this<b))?1:0);
    }
    bigint mov(long long x)
    {
        bigint ans;
        ans.num.clear();
        ans.num.resize(num.size()+x);
        for (long long i=0,size=num.size();i<size;i++)
            if (i+x>=0)
                ans.num[i+x]=num[i];
        return ans;
    }
    bigint operator = (long long b)
    {
        char s[20+1];
        sprintf(s,"%lld",b);
        num.clear();
        num.resize(strlen(s));
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(s[size-1-i]-'0');
        return (*this);
    }
    bigint operator = (string b)
    {
        num.clear();
        num.resize(b.size());
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(b[size-1-i]-'0');
        return (*this);
    }
    bigint operator + (bigint b)
    {
        bigint ans;
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)+((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
        {
            if (ans.num[i]>=10&&i==size-1)
                ans.num.resize(++size);
            ans.num[i+1]+=(ans.num[i]/10);
            ans.num[i]%=10;
        }
        return ans;
    }
    bigint operator += (bigint b)
    {
        return (*this=(*this+b));
    }
    bigint operator - (bigint b)
    {
        bigint ans;
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)-((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            while (ans.num[i]<0)
                ans.num[i]+=10,ans.num[i+1]--;
        while (ans.num[ans.num.size()-1]==0)
            ans.num.resize(ans.num.size()-1);
        return ans;
    }
    bigint operator -= (bigint b)
    {
        return (*this=(*this-b));
    }
    bigint operator * (bigint b)
    {
        bigint ans,num_0;
        num_0=0;
        ans.num.clear();
        if (*this!=num_0&&b!=num_0)
        {
            ans.num.resize(num.size()+b.num.size()-1);
            for (unsigned long long i=0,size_1=num.size();i<size_1;i++)
                for (unsigned long long j=0,size_2=b.num.size

();j<size_2;j++)
                    ans.num[i+j]+=(num[i]*b.num[j]);
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
        }
        else
            ans=0;
        return ans;
    }
    bigint operator *= (bigint b)
    {
        return (*this=(*this*b));
    }
    bigint operator / (bigint b)
    {
        bigint ans,num_0;
        num_0=0;
        ans.num.clear();
        if (*this!=num_0&&*this>num_0)
        {
            ans.num.resize(num.size());
            bigint x,y;
            x=*this,y=b.mov(num.size()-b.num.size());
            unsigned long long rec=0;
            for (unsigned long long ci=0,i=num.size()-1,temp=0;ci<=num.size()-

b.num.size();ci++,rec=i,i-=temp)
            {
                if (temp==0)
                {
                    if (x>=y)
                        temp=1;
                }
                while (x>=y)
                    x-=y,ans.num[i]++;
                y=y.mov(-1);
            }
            ans=ans.mov(-rec);
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
        }
        else if (*this!=num_0&&*this==num_0)
            ans=1;
        else
            ans=0;
        return ans;
    }
    bigint operator /= (bigint b)
    {
        return (*this=(*this/b));
    }
    void print()
    {
        for (unsigned long long i=0,size=num.size();i<size;i++)
            printf("%d",num[size-1-i]);
    }
};

int n,w;
bigint ans;
bigint c[(1<<9)+1][(1<<9)+1];

int main()
{
    while (~scanf("%d%d",&n,&w))
    {
        for (int i=0;i<=(1<<n);i++)
            for (int j=0;j<=(1<<n);j++)
                c[i][j]=0;
        for (int i=1;i<=(1<<n);i++)
        {
            c[i][0]=c[i][i]=1;
            for (int j=1;j<i;j++)
                c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
        ans=0;
        for (int i=2;i<=w/n&&i<(1<<n);i++)
            ans+=c[(1<<n)-1][i];
        for (int i=1;i<(1<<(w%n))&&w/n<(1<<n)-i;i++)
            ans+=c[(1<<n)-i-1][w/n];
        ans.print();
        printf("\n");
    }
}

/*

Author: Slience_K
Belong: C++
Pro: NOIP 2006 - 4

*/
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const int INF = ( int )( 1e9 );
int c[ 600 ][ 600 ][ 50 ] , ans[ 50 ];
int w , k;
void Add( int a[] , int b[] , int z[] ){
z[ 0 ] = max( a[ 0 ] , b[ 0 ] );
for( int i = 1 ; i <= z[ 0 ] ; i++ ){
z[ i ] += a[ i ] + b[ i ];
z[ i + 1 ] += z[ i ] / INF;
z[ i ] %= INF;
}
if ( z[ z[ 0 ] + 1 ] ) z[ 0 ]++;
}
void Plus( int a[] ){
ans[ 0 ] = max( ans[ 0 ] , a[ 0 ] );
for( int i = 1 ; i <= ans[ 0 ] ; i++ ){
ans[ i ] += a[ i ];
ans[ i + 1 ] += ans[ i ] / INF;
ans[ i ] %= INF;
}
if ( ans[ ans[ 0 ] + 1 ] ) ans[ 0 ]++;
}
int main(){
scanf( "%d%d" , &k , &w );
c[ 1 ][ 0 ][ 1 ] = c[ 1 ][ 1 ][ 1 ] = 1;
c[ 1 ][ 0 ][ 0 ] = c[ 1 ][ 1 ][ 0 ] = 1;
for( int i = 2 ; i <= ( 1 << k ) ; i++ )
for( int j = 0 ; j <= i ; j++ )
if ( j == 0 ) c[ i ][ j ][ 0 ] = c[ i ][ j ][ 1 ] = 1;
else Add( c[ i - 1 ][ j ] , c[ i - 1 ][ j - 1 ] , c[ i ][ j ] );
for( int i = 2 ; i <= w / k ; i++ )
Plus( c[ ( 1 << k ) - 1 ][ i ] );
for( int i = 1 ; i <= ( 1 << ( w % k ) ) - 1 ; i++ )
Plus( c[ ( 1 << k ) - i - 1 ][ w / k ] );
printf( "%d" , ans[ ans[ 0 ] ] );
for( int i = ans[ 0 ] - 1 ; i >= 1 ; i-- )
printf( "%09d" , ans[ i ] );
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 109 ms, mem = 231152 KiB, score = 10
测试数据 #1: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
测试数据 #2: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 231144 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 231148 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 231152 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
Accepted, time = 931 ms, mem = 231152 KiB, score = 100

高精度＋预处理组合数计算(帕斯卡公式)
。。。其实几乎所有时间都是预处理，不过可以压下位，懒得写了(其实也没写过）

组合+高精
#include <iostream>
#include <cstdio>
using namespace std;

int c[512][512][100];
void plus1(int x[],int y[],int z[]){

z[0]=max(x[0],y[0]);
for(int i=1;i<=z[0];i++)
{
z[i]+=x[i]+y[i];
z[i+1]+=z[i]/10;
z[i]%=10;

}

if(z[z[0]+1]!=0)z[0]++;

}
void plus2(int x[],int y[])
{
x[0]=max(x[0],y[0]);
for(int i=1;i<=x[0];i++)
{
x[i]+=y[i];
x[i+1]+=x[i]/10;
x[i]%=10;

}

if(x[x[0]+1]!=0)x[0]++;
}

int main(){
int k,n,bmax,hmax,ans[201]={0};
cin>>k>>n;
bmax=1<<k;
hmax=1<<(n%k);
c[0][0][0]=c[0][0][1]=1;
for(int i=1;i<bmax;i++)
for(int j=0;j<=i;j++)
{
if(j==0)c[i][j][0]=c[i][j][1]=1;
else plus1(c[i-1][j],c[i-1][j-1],c[i][j]);
}
for(int i=2;i<=n/k&&i<bmax;i++)plus2(ans,c[bmax-1][i]);
for(int i=1;i<hmax&&n/k+i<bmax;i++)plus2(ans,c[bmax-i-1][n/k]);
for(int i=ans[0];i>=1;i--)printf("%d",ans[i]);

return 0;
}

Block code

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
struct num{
int len, a[210];
num(int x = 0) {
len = 0;
memset(a, 0, sizeof(a));
while (x) {
a[++len] = x % 10;
x /= 10;
}
}
void print() {
for (int i = len; i > 0; i--) printf("%d", a[i]); printf("\n");
}
} c;
num operator * (const num & a, int b) {
c = num(0);
for (int i = 1; i <= a.len || c.a[i] != 0; i++) {
c.a[i] += a.a[i]*b;
c.a[i+1] += c.a[i] / 10;
c.a[i] %= 10;
c.len = i;
}
return c;
}
num operator / (const num & a, int b) {
c = a;
for (int i = a.len; i > 0; i--) {
c.a[i-1] += c.a[i] % b * 10;
c.a[i] /= b;
}
while (c.a[c.len] == 0) c.len--;
return c;
}
num operator - (const num & a, const num & b) {
c = a;
for (int i = 1; i <= a.len; i++) {
c.a[i] -= b.a[i];
if (c.a[i] < 0) c.a[i] += 10, c.a[i+1]--;
}
while (c.a[c.len] == 0) c.len--;
return c;
}
num operator + (const num & a, const num & b) {
c = num(0);
for (int i = 1; i <= a.len || i <= b.len || c.a[i] != 0; i++) {
c.a[i] += a.a[i]+b.a[i];
c.a[i+1] += c.a[i] / 10;
c.a[i] %= 10;
c.len = i;
}
return c;
}
int main() {
freopen("2knum.in", "r", stdin);
freopen("2knum.out", "w", stdout);
int k, w;
scanf("%d%d", &k, &w);
num t, ans(0);
int m = (1<<k)-1;
t = num(m);
for (int i = 2; i <= (w/k)+1; i++) {
t = t * (--m) / i;
ans = ans + t;
// ans.print();
}
m = (1<<k) - (1<<(w%k));
t = num(m);
for (int i = 2; i <= (w/k)+1; i++) t = t * (--m) / i;
// t.print();
ans = ans - t;
ans.print();
return 0;
}

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
struct num{
int len, a[210];
num(int x = 0) {
len = 0;
memset(a, 0, sizeof(a));
while (x) {
a[++len] = x % 10;
x /= 10;
}
}
void print() {
for (int i = len; i > 0; i--) printf("%d", a[i]); printf("\n");
}
} c;
num operator * (const num & a, int b) {
c = num(0);
for (int i = 1; i <= a.len || c.a[i] != 0; i++) {
c.a[i] += a.a[i]*b;
c.a[i+1] += c.a[i] / 10;
c.a[i] %= 10;
c.len = i;
}
return c;
}
num operator / (const num & a, int b) {
c = a;
for (int i = a.len; i > 0; i--) {
c.a[i-1] += c.a[i] % b * 10;
c.a[i] /= b;
}
while (c.a[c.len] == 0) c.len--;
return c;
}
num operator - (const num & a, const num & b) {
c = a;
for (int i = 1; i <= a.len; i++) {
c.a[i] -= b.a[i];
if (c.a[i] < 0) c.a[i] += 10, c.a[i+1]--;
}
while (c.a[c.len] == 0) c.len--;
return c;
}
num operator + (const num & a, const num & b) {
c = num(0);
for (int i = 1; i <= a.len || i <= b.len || c.a[i] != 0; i++) {
c.a[i] += a.a[i]+b.a[i];
c.a[i+1] += c.a[i] / 10;
c.a[i] %= 10;
c.len = i;
}
return c;
}
int main() {
int k, w;
scanf("%d%d", &k, &w);
num t, ans(0);
int m = (1<<k)-1;
t = num(m);
for (int i = 2; i <= (w/k)+1; i++) {
t = t * (--m) / i;
ans = ans + t;
// ans.print();
}
m = (1<<k) - (1<<(w%k));
t = num(m);
for (int i = 2; i <= (w/k)+1; i++) t = t * (--m) / i;
// t.print();
ans = ans - t;
ans.print();
return 0;
}

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxw=30001;
const int maxk=1025;
#include <vector>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
using namespace std;
struct BigInteger
{
static const int BASE=100000000;
static const int WIDTH=8;
vector<int> s;

BigInteger(long long num=0) {*this=num;}
BigInteger operator = (long long num)
{
s.clear();
do
{
s.push_back(num%BASE);
num/=BASE;
}while(num>0);
return *this;
}
BigInteger operator = (const string& str)
{
s.clear();
int x,len=(str.length()-1)/WIDTH+1;
for(int i=0;i<len;i++)
{
int end=str.length()-i*WIDTH;
int start=max(0,end-WIDTH);
sscanf(str.substr(start,end-start).c_str(),"%d",&x);
s.push_back(x);
}
return *this;
}

bool operator < (const BigInteger& b) const
{
if(s.size()!=b.s.size()) return s.size()<b.s.size();
for(int i=s.size()-1;i>=0;i--)
if(s[i]!=b.s[i]) return s[i]<b.s[i];
return false;
}

BigInteger operator + (const BigInteger& b) const
{
BigInteger c;
c.s.clear();
for(int i=0,g=0;;i++)
{
if(g==0 && i>=s.size() && i>=b.s.size()) break;
int x=g;
if(i<s.size()) x+=s[i];
if(i<b.s.size()) x+=b.s[i];
c.s.push_back(x%BASE);
g=x/BASE;
}
return c;
}

BigInteger operator - (const BigInteger& b) const

{
BigInteger c;
c.s.clear();
for(int i=0,g=0;;i++)
{
if(g==0 && i>=s.size() && i>=b.s.size()) break;
int x=s[i]+g;
if(i<b.s.size())
{
x-=b.s[i];
if(x<0) {x+=10; g=-1;} else g=0;
}
c.s.push_back(x%BASE);
}
return c;
}

BigInteger operator += (const BigInteger& b)
{
*this=*this+b; return *this;
}
};
ostream& operator << (ostream &out, const BigInteger& x)
{
out<<x.s.back();
for(int i=x.s.size()-2;i>=0;i--)
{
char buf[20];
sprintf(buf,"%08d",x.s[i]);
for(int j=0;j<strlen(buf);j++) out<<buf[j];
}
return out;
}
istream& operator >> (istream &in, BigInteger&x)
{
string s;
if(!(in>>s)) return in;
x=s;
return in;
}
int k,w;
BigInteger c[maxw][maxk];
int main()
{
scanf("%d %d",&k,&w);
int q=1<<k,n=min(w/k,q-2),m=w%k;
c[0][0]=1; c[1][0]=1; c[0][1]=1; c[1][1]=1;
for(int i=2;i<=q;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
BigInteger ans=0;
for(int i=2;i<=n+1;i++)
ans+=c[q-1][i];
ans=ans-c[q-(1<<m)][n+1];
cout<<ans;
return 0;
}

var
i,j,n,m,x,y,z,l,k:longint;o:int64;flag:boolean;
a:array[-1..1,1..520,1..25]of longint;
procedure jia(e,f,g,h:longint); var i:longint;
begin for i:=1 to 25 do a[e,f,i]:=a[e,f,i]+a[g,h,i];
for i:=1 to 25 do if a[e,f,i]>=100000000 then begin
a[e,f,i+1]:=a[e,f,i+1]+a[e,f,i]div 100000000;
a[e,f,i]:=a[e,f,i]mod 100000000;end;end;
procedure clear(e,f:longint); var i:longint;
begin for i:=1 to 25 do a[e,f,i]:=0;end;
procedure cop(e,f,g,h:longint);var i:longint;
begin for i:=1 to 25 do a[e,f,i]:=a[g,h,i];end;
function fu(e:longint):longint;
begin if e=y then exit(x);exit(z-i);end;
begin
readln(n,m); z:=1;for i:=1 to n do z:=2*z;dec(z);
x:=1;for i:=1 to m mod n do x:=2*x;dec(x);
if m mod n=0 then x:=z;
if m mod n<>0 then y:=m div n+1 else y:=m div n;if y>z then y:=z;
for i:=1 to z do a[0,i,1]:=1;
for i:=2 to y do begin l:=l xor 1;
clear(l,z-i+1);jia(l,z-i+1,l xor 1,z-i+2);
if z-i<=fu(i) then jia(-1,1,l xor 1,z-i+2);
for j:=z-i downto 1 do begin cop(l,j,l,j+1);jia(l,j,l xor 1,j+1);
if j<=fu(i) then jia(-1,1,l,j);end;end;
for i:=25 downto 1 do if flag or(a[-1,1,i]<>0) then begin
if flag then for j:=1 to 8 do begin o:=a[-1,1,i];
for k:=1 to j do o:=o*10;if o<100000000 then write('0')else break;end;
write(a[-1,1,i]);flag:=true;end;
end.
可以将数组压缩
FROM ADAM

const py=1000000;
type dd=array[0..35] of longint;
var
k,w,m,i,m1:longint;
f:array[0..513,0..513] of dd;
ans:dd;
function add(a,b:dd):dd;
var i,len:longint;
begin
fillchar(add,sizeof(add),0);
if a[0]>b[0] then len:=a[0]
else len:=b[0];
for i:=1 to len do
begin
add[i]:=add[i]+a[i]+b[i];
add[i+1]:=add[i] div py;
add[i]:=add[i] mod py;
end;
if add[len+1]>0 then inc(len);
add[0]:=len;
end;
procedure c(n:longint);
var i,j:longint;
begin
fillchar(f,sizeof(f),0);
f[0,0][0]:=1; f[0,0][1]:=1;
for i:=1 to n do
for j:=0 to i do
if j=0 then begin f[i,j][0]:=1; f[i,j][1]:=1; end
else f[i,j]:=add(f[i-1,j-1],f[i-1,j]);
// exit(f[n,m]);
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;

begin
readln(k,w);
m:=1; for i:=1 to k do m:=m*2; m:=m-1;

c(m);
for i:=2 to min(m,w div k) do
ans:=add(ans,f[m,i]);
m1:=1;
for i:=1 to w mod k do
m1:=m1*2;
m1:=m1-1;
for i:=1 to m1 do
ans:=add(ans,f[m-i,min(m,w div k)]);
write(ans[ans[0]]);
for i:=ans[0]-1 downto 1 do
begin
if ans[i]<10 then write('0');
if ans[i]<100 then write('0');
if ans[i]<1000 then write('0');
if ans[i]<10000 then write('0');
if ans[i]<100000 then write('0');
write(ans[i]);
end;
end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 649ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：649ms

递推+滚动数组+压位高精

f表示第I位上为J时进制数的个数,具体自己想...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 728ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

递推+滚动数组+压位高精加。。

滚动数组其实根本不会写- -||||

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

强大的评测机。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

直接用公式算秒杀。。。

ans:=C(m,i)(2

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：150ms

~~

过不去~

差距这么大.......

sunny:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 509ms

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：509ms

puppy:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：253ms

让我很无语啊

f表示有i位数字,最高位与最低位差小于j的符合条件的总数.

f有两部分组成,

一个是f,因为定义里面是小于j

另一个就是f,

这就相当于少用一个数字,少了数字,差就必然少1

所以f=f+f

边界条件

f=1

f[1,i]=i+1

最终答案只要分两部分来求,

除掉不能被k整除的最高位,设其为p,该位最大为q

另一部分是能被整除的剩下几位.

对于后者,求和f (i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms