题解 | 信息学奥赛一本通 2^k 进制数

思路

跑动态规划.表示第位的数位,前位已经确认的数的个数.
转移应该挺好转移的,需要用前缀和优化一下.内存可能比较大,需要滚动数组.
最后把满足要求的答案全部加起来就可以了.
复杂度为,看起来比较大,实际上基本上跑不满,还是可以过的.

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXL 505

struct bignum{
    int len, a[MAXL];
    bignum(){
        memset( a, 0, sizeof a );
        len = 1;
    }
    friend bignum operator + ( bignum x, bignum y ){
        bignum t;
        t.len = max( x.len, y.len );
        for ( int i = 1; i <= t.len; ++i ){
            t.a[i] += x.a[i] + y.a[i];
            t.a[i + 1] += t.a[i] / 10;
            t.a[i] %= 10; 
        }
        if ( t.a[t.len + 1] ) t.len++;
        return t;
    }
};

int k, W;
bignum f[600];
bignum ans;

int main(){
    scanf( "%d%d", &k, &W );
    for ( int i = 1; i < 1 << k; ++i ) f[i].a[1] = 1;
    W = min( W, ( ( 1 << k ) - 1 ) * k );
    for ( int i = 2; i <= ( W - 1 ) / k + 1; ++i ){
        bignum t, tt; t = f[(1 << k) - i + 2];
        for ( int j = ( 1 << k ) - i + 1; j >= 1; --j ){
            tt = t + f[j]; f[j] = t; t = tt;
            if ( i != ( W - 1 ) / k + 1 || W % k == 0 ) ans = ans + f[j];
        }
    }

    if ( W % k ) for ( int i = 1; i < 1 << ( W % k ); ++i ) ans = ans + f[i];

    for ( int i = ans.len; i >= 1; --i ) printf( "%d", ans.a[i] );
    return 0;
}