noi.ac #741 code

挺有价值的 \(dp\) 题。

设 \(f[i][j]\) 是 \(01\) 串的前 \(i\) 位构成的子串形成了 \(j\) 这个数的可能性数量。

对 \(i\) 进行倒序枚举，可以得到 \(dp\) 方程 ：
\[f[i][j] = f[i][j] + f[k-1][j-tmp]\]

其中 \(1\le k \le i,1 \le i \le n, 1 \le j \le m\)。\(tmp\) 为剩下的部分组成的数 。

最后的答案就是 \(\sum\limits_{i=1}^mf[n][i]\) 。

记得取膜。。。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 998244353;
const int N = 3010;
ll n, m;
char ch[N];
ll f[N][N];//f[i][j]表示01串用前i位构成的j这个数有几种可能
int main() {
    cin >> m;
    cin >> ch + 1;
    n = strlen(ch + 1);
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int tmp = 0;
            for(int k = i; k >= 1; k--) {
                if(ch[k] == '0') continue;
                else tmp += (1 << (i - k));//对j这个数进行拆分
                if(tmp > j) break;
                else {
                    f[i][j] += f[k-1][j-tmp];//少一位，枚举这一位
                    f[i][j] %= mod;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= m; i++) ans = (ans + f[n][i]) % mod;
    printf("%lld\n",ans * 2 % mod);
    return 0;
}