调了2个多小时。QAQ

写的类似数位dp的记忆化搜索。

思路很好想。

定义f[i][j]为长度为i，最高位是j的合法数字的方案数。

转移就是f[i][j]=∑f[i-1]k.

时间复杂度是状态数（位数x最高位=500x500）x状态计算（高精度x最高位=?x500）

大概是1e10左右，不过这是最坏情况，实际情况要少的多。

不写高精度的话能得80分。主要是高精度调了半天。

写string能得80分，剩下2个点都TLE（相到于没写）。

写vector能得90分，还是T了一个点开O2勉强卡过。

最后拿数组写的，尽可能压位的话跑的还可以。

//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef unsigned long long ull;
const ull mod=1e18;
int K,w,limit1,limit2,l;
struct Big
{
    int len;
    ull A[21];
}f[630][630],ans;

inline void init(Big &x)
{
    x.len=1; x.A[1]=0;
    return ;
}

inline Big add(Big a1,Big a2)
{
    Big sum; int len1=min(a1.len,a2.len),last=0;
    for(int i=1;i<=len1;++i)
    {
        sum.A[i]=a1.A[i]+a2.A[i]+last;
        if(sum.A[i]>mod){ sum.A[i]-=mod; last=1;}
        else last=0;
    }
    int len2=max(a1.len,a2.len); sum.len=len2;
    if(a1.len<a2.len)
        for(int i=len1+1;i<=len2;++i)
        {
            sum.A[i]=a2.A[i]+last;
            if(sum.A[i]>mod){ sum.A[i]-=mod; last=1;}
            else last=0;
        }
    else
        for(int i=len1+1;i<=len2;++i)
        {
            sum.A[i]=a1.A[i]+last;
            if(sum.A[i]>mod){ sum.A[i]-=mod; last=1;}
            else last=0;
        }
    if(last){ sum.A[++sum.len]=1; }
    return sum;
}

inline Big dfs(int x,int len)   //最高位是x长度为len的数的个数
{
    if(f[x][len].len) return f[x][len];
    if(len==1){ init(f[x][len]); f[x][len].A[1]=1; return f[x][len];}
    if(limit2-x<len-1){ init(f[x][len]); return f[x][len]; }
    Big res; init(res); 
    for(int i=x+1;i<=limit2-len+2;++i)
        res=add(res,dfs(i,len-1));
    f[x][len]=res;
    return res;
}

inline void write(Big x)
{
    int len=x.len;
    printf("%llu",x.A[len]);
    for(int i=len-1;i;--i)
        printf("%018llu",x.A[i]);
    return ;
}

int main(void)
{
    //freopen("test.in","r",stdin);
    scanf("%d%d",&K,&w);
    l=w/K+((w%K)?1:0);
    limit1=w%K; if(!limit1) limit1+=K; 
    limit1=pow(2,limit1)-1; 
    limit2=pow(2,K)-1; init(ans);
    for(int i=2;i<=l;++i)   //枚举位数
        for(int j=1;j<=((i==l)?limit1:limit2);++j)  //枚举最高位
            ans=add(ans,dfs(j,i));
    write(ans); printf("\n");
    return 0;
}