题目
牢骚
现在是 2021.12.5 距离 NOIP2021 结束已经过去了两周零一天。
自从 NOIP 结束之后，我就在一直麻痹自己，在这两周停竞赛补文化课的时间里，我也渐渐冷静了下来。
T2 没做出来没什么，我不是还补了 \(60pts\) 的暴力吗？这样还有个机会混个省一。
今天是这两周以来第二次来机房，上一次是出成绩的那一天，我知道我 T2 爆弹之后径直走出了机房，嘴里不停念叨着 impossible。
我没有勇气点开我 T2 的代码，疑惑，愤怒，懊悔，无奈，去年的 NOIP ，我也是 T2 爆零而滚出省一，参加了对我们这一届最有希望但对我毫无希望的省选。
也许这就是命。
回过神来，尽管我早已预料到我会以一个失败者的身份离开这个舞台，但我不愿以一个落魄者的身份离开。
我回来了，在今天上午，我看了看 T2 的代码，没输出答案，呵，多么愚蠢的错误。
然后我独立做出来了这道题，尽管我还有些考 NOIP 时没有的头痛。
我告诉自己：至少我也签到成功了，尽管是补签。算是增添了一点信心。
虽然目的不是写题解，但是这里是写题解的地方，而不是让笔者来发牢骚的，所以接下来是题解。
讲解
这道题确实把做法写脸上了，是一道合格的签到题。
二进制状态，\(1\) 的个数，选了多少个数，这些信息都需要知道，所以直接放状态里面就好了。
令 \(dp_{i,S,j,k}\) 表示考虑到第 \(i\) 个数，从这里开始往后的二进制状态为 \(S\)，共有 \(j\) 个 \(1\)，现在选了 \(k\) 个数。
我们需要意识到这样一件事：\(2^{\log_2n}=n\)，然后就结束了，因为这就代表了 \(S\) 的大小为 \(n\) 而并非 \(2^n\)。
对于计数，我们有众所周知的公式：\(\frac{n!}{\prod cnt_{i}}\)，\(\frac{1}{\prod cnt_i}\) 是每一项带的系数， \(n!\) 只需要最后乘上去即可，本质上是组合数。
转移很显然，就不写了。时间复杂度 \(O(n^4m)\)。
代码
补签代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 105;
const int MOD = 998244353;
int n,m,kk,ans;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int a[MAXN],ifac[MAXN],fac[MAXN];
int dp[105][35][35][35],cnt[MAXN],mi[MAXN][MAXN];
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y&1)ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
void init(int x)
{
fac[0] = ifac[0] = 1;
for(int i = 1;i <= x;++ i) fac[i] = 1ll * fac[i-1] * i % MOD;
ifac[x] = qpow(fac[x],MOD-2);
for(int i = x-1;i >= 1;-- i) ifac[i] = ifac[i+1] * (i+1ll) % MOD;
for(int i = 1;i <= x;++ i) cnt[i] = cnt[i>>1] + (i&1);
for(int i = 0;i <= m;++ i)
for(int j = 0;j <= x;++ j)
mi[i][j] = qpow(a[i],j);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read(); kk = Read();
for(int i = 0;i <= m;++ i) a[i] = Read();
init(100);
dp[0][0][0][0] = 1;
for(int i = 0;i <= m;++ i)//第i种
for(int S = 0;S <= n;++ S)//状态S
for(int j = 0;j <= n;++ j)//j个1
for(int k = 0;k <= n;++ k)//k个数
for(int l = 0;l <= n-k;++ l)//当前选l个
(dp[i+1][(S+l)>>1][j+cnt[S+l]-cnt[S]][k+l] += 1ll * dp[i][S][j][k] * ifac[l] % MOD * mi[i][l] % MOD) %= MOD;
for(int S = 0;S <= n;++ S)
for(int j = 0;j <= kk;++ j)
ans = (ans + dp[m+1][S][j][n]) % MOD;
Put(1ll * ans * fac[n] % MOD,'\n');
return 0;
}