[CSP-S2019] Emiya 家今天的饭

同步发于luogu blog

（又不交题解，何必在意格式呢233）

之前场上毫无头绪的题，经 sh 推荐三年后第一次再点开这题，发现特别容易。

这个 \(<k/2\) 的限制非常难搞，首先考虑容斥一下，算不合法方案数，这样就至多有一个 \(>k/2\) 了。

然后考虑枚举那个不符合的食材，考虑dp。\(dp_{i,j,k}\) 表示 前i种菜品，做了j道菜，做了k道钦定的食材的菜，这样dp是\(mn^3\)的，可以有 \(84\) 分。再想一想发现你只需要记录 \(k-j\) 的差值就可以了，于是可以去掉以为，复杂度就是 \(mn^2\) 了，就过了？

int all=1;
		rdn;rdm;upn upm rd(a[i][j]),sm[i]+=a[i][j],sm[i]%=mod;
		upn all*=(sm[i]+1),all%=mod;
		all--;all+=mod;all%=mod;
		up(p,1,m)
		{
			memset(dp,0,sizeof(dp));
			dp[0][n]=1;
			up(i,1,n)
			{
				up(J,-n,n)
				{
					int j=J+n;
					if(!dp[i-1][j])continue;
					int val=dp[i-1][j];
					Add(dp[i][j],val);
					Add(dp[i][j-1],val*(sm[i]-a[i][p]+mod)%mod);
					Add(dp[i][j+1],val*a[i][p]%mod);
				}
			}
			up(j,1,n)
			{
				Sub(all,dp[n][j+n]);
			}
		}
		cout<<all;edl;

为什么这么简单？？？

希望明天不要像以前一样降智。

原文地址：http://www.cnblogs.com/MatrixCascade/p/16837379.html