今年CSP我不想说了，想AFO
我看了很久luogu题解，才略微懂了点
首先这是一道dp考场上没看出来？
思路分析
1.Emiya的条件很容易满足。
2.Rin的条件也是比较死的，同一烹饪方法只有一种菜（也就是输入中的每一行只有一个菜）
3.Yazid的要求很特殊，先不考虑。
可以看出，维护每列已选的节点复杂度太大，不太可行；因此很容易想到，先不考虑每列不超过一半的这个限制，求出总方案数，然后再减去考虑这个限制后不合法的方案数。现在问题就变成，求任意列选的节点超过所有选的节点的一半的方案数之和。
总数：每行的可能数相乘。见下代码。
for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=read(); sum[i]=(a[i][j]+sum[i])%mod; //每种烹饪一共能做多少菜 } ans=(ans*(sum[i]+1))%mod; //sum[i]+1是因为可以不用某种烹饪 } ans--; //ans-1是因为不能一样菜都没有
接下来咋处理？
设f[i][j][k]表示前i行选j个节点，当前枚举到的列选k个节点的方案数。对于每个列，复杂度为O($n^3$)，总的复杂度为O($mn^3$)，可以得到84分的高分。
要拿满分怎么办？
考虑将某两个状态合并！！！“观察状态，实际上我们想知道的只是j,k的大小关系（即k>
⌊j/2⌋ ），对于具体的值并不关心，考虑将它们合并到一维。” 考虑我们需要的限制条件j>⌊k/2⌋ ，变形一下可以得到2*k+n-j>n。观察这个式子，可以发现，n−j就是这n行里没有选的行数。2*k就只需要存两次就行了
然后一个奇妙的想法就出来了：
对于每个节点，选它时，当做该列选了两次。
而对于某一行不选时，当做所有列选了一次。
最终要找的就是当前列被选超过n次的方案。这样就成功地优化掉了第二维。
f[i][k]=(f[i][k]+f[i-1][k]*(sum[i]-a[i][j]))%mod;//若不选此列，所以总次数是每行除开a[i][j]外的任何数之积。 f[i][k+1]=(f[i][k+1]+f[i-1][k])%mod;//若不选此行，总次数是i-1行的方案，和这一行没任何关系，直接改变k+1的值 f[i][k+2]=(f[i][k+2]+f[i-1][k]*a[i][j])%mod; //若要选节点，同上面的两次分i-1行的值乘上该节点值，也就是k+2的值了
注意：开long long
代码如下：
#include<cstdio> #include<string> #define ll long long using namespace std; const int maxn=105,maxm=2005,mod=998244353; int n,m; ll a[maxn][maxm]; ll sum[maxn]; ll ans=1; ll f[maxn][maxm]; int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } void readdata() { n=read(),m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=read(); sum[i]=(a[i][j]+sum[i])%mod; } ans=(ans*(sum[i]+1))%mod; } ans--; for(int j=1;j<=m;j++) { memset(f,0,sizeof(f)); f[0][0]=1; for(int i=1;i<=n;i++) { for(int k=0;k<=(i-1)<<1;k++) //第i行可能涉及到(i-1)*2，"<<1"相当于“*2” { f[i][k]=(f[i][k]+f[i-1][k]*(sum[i]-a[i][j]))%mod; f[i][k+1]=(f[i][k+1]+f[i-1][k])%mod; f[i][k+2]=(f[i][k+2]+f[i-1][k]*a[i][j])%mod; } } for(int k=n+1;k<=2*n;k++) { ans=(ans-f[n][k]+mod)%mod; //每次会重复 } } printf("%lld",ans%mod); } int main() { readdata(); return 0; }
AFO^……