记录编号	593828	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2021]数列	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	1.461 s
提交时间	2024-09-17 14:59:51	内存使用	10.60 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int MOD = 998244353;
int n = mread(), m = mread(), k = mread(), f[105][35][35][35], a[105], fac[35], ifac[35];
int ksm(int x, int k){
    int ans = 1, now = x;
    while(k){
        if(k & 1){
            ans = ans * now % MOD;
        }
        now = now * now % MOD;
        k >>= 1;
    }
    return ans;
}
int C(int n, int m){
    return fac[n] * ifac[n - m] % MOD * ifac[m] % MOD;
}
signed main(){
    fac[0] = ifac[0] = 1;
    for(int i = 1; i < 35; i ++){
        fac[i] = fac[i - 1] * i % MOD;
        ifac[i] = ksm(fac[i], MOD - 2);
    }
    m ++;
    for(int i = 1; i <= m; i ++){
        a[i] = mread();
    }
    f[1][0][0][0] = 1;
    for(int i = 1; i <= m; i ++){
        int pw[35];
        pw[0] = 1;
        for(int j = 1; j <= 30; j ++){
            pw[j] = pw[j - 1] * a[i] % MOD;
        }
        for(int j = 0; j <= n; j ++){
            for(int l = 0; l <= k; l ++){
                for(int now = 0; now <= 32; now ++){
                    // 前 i 个 v_i，a 数组大小已经为 j，sum 中除了 now 中的还有 l 个 1
                    for(int o = 0; o <= n - j; o ++){
                        int vnow = (now + o);
                        int vj = j + o;
                        int vl = l + (vnow & 1);
                        vnow >>= 1;
                        if(vl <= k){
                            (f[i + 1][vj][vl][vnow] += f[i][j][l][now] * pw[o] % MOD * C(n - j, o) % MOD) %= MOD;
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= k; i ++){
        for(int now = 0; now <= 32; now ++){
            if(__builtin_popcount(now) + i <= k){
                (ans += f[m + 1][n][i][now]) %= MOD;
                // printf("*** %lld %lld %lld %lld %lld\n", m + 1, n, i, now, f[m + 1][n][i][now]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}