[NOIP2021] 数列
废物着实是我，我确也是废物。
除了原题，我连联赛题做出来的可能都没有。
这就更废物了。
所以我直接废物躺了。
因为从来没有见过类似的 DP 题，考场上我只用 naive 的思路去想这个题。
结果回来一复盘，哦豁，这个状态怎么还能这样定，还有这状态的转移怎么这么怪。。。
回过头来一想，才发现自己考场上想的思路全都是按自己的做题经验想的，根本不可能想到这种转移。。。
背题家实锤。。。马上连题都不会背了。。。
技不如人，甘拜下风。欢声笑语打出 gg。
定义状态 $f(i,j,k,p)$ 表示考虑到 $v_i$，现在序列考虑到了第 $j$ 个位置，第 $i$ 位及之前的 1 的个数为 $k$，并且这一位将要向下一位转移 $p$ 个 1。
然后这个直接往外推就完了，假设我们选了 $t$ 个 $i$：
$$f(i,j,k,p)\cdot v_i^t\cdot \binom{n-j}{t}\rightarrow f(i+1,j+t,k+(t+p)\bmod 2,\lfloor\dfrac{t+p}{2}\rfloor)$$
显然这个方程想转化为一个 $f(i,j,k,p)$ 的表达式并不是很现实。
然而我考场上接近一半的时间都在思考这种转移方式。
然后初态就是 $f(0,0,0,0)=1$。
最后把答案统计起来需要再数一下最后进的二进制位数。。。
反正跑不满，写了个快速幂，其实和常数差不多吧。。。
时间复杂度 $O(n^3mk)$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=30,M=1e2,mo=998244353;
ll n,m,k_,ans;
ll c[N+5][N+5],f[2][N+5][N+5][N+5],v[M+5];
inline ll qpow(ll b,ll p) {
ll res=1;while(p){if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}
inline void Init() {
c[0][0]=1;
for(ll i=1;i<=N;i++) {
c[i][0]=1;
for(ll j=1;j<=i;j++) {
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
}
}
}
inline ll Bitcnt(ll x) {ll cnt=0;for(;x;x-=x&-x,cnt++);return cnt;}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
int main() {
Init();
n=read();m=read();k_=read();
for(ll i=0;i<=m;i++) v[i]=read();
f[0][0][0][0]=1;
for(ll i=0;i<=m;i++) {
for(ll j=0;j<=n;j++) {
for(ll k=0;k<=k_;k++) {
for(ll p=0;p<=(n>>1);p++) {
for(ll t=0;t<=n-j;t++) {
f[(i+1)&1][j+t][k+(t+p)%2][(t+p)/2]=
(f[(i+1)&1][j+t][k+(t+p)%2][(t+p)/2]
+f[i&1][j][k][p]*qpow(v[i],t)%mo*c[n-j][t]%mo)%mo;
}
}
}
}
for(ll j=0;j<=n;j++) {
for(ll k=0;k<=k_;k++) {
for(ll p=0;p<=(n>>1);p++) {
f[i&1][j][k][p]=0;
}
}
}
}
for(ll k=0;k<=n;k++) {
for(ll p=0;p<=(n>>1);p++) {
if(Bitcnt(p)+k<=k_) ans=(ans+f[(m+1)&1][n][k][p])%mo;
}
}
write(ans);
return 0;
}
|