题解 P5784 【[CQOI2008]矩阵的个数】
UnyieldingTrilobite
·
·
题解
Update:2020.2.28,修复错别字，麻烦管理员重新过下！
好像只有一篇过不了样例的题解。
据说是为了防抄袭稍改了一下。
那就让本juruo来一篇高清无注释能AC方便直接复制粘贴的题解吧！
大概说说思路，具体的珂以根据代码看/自己思考（如果一步步跟着想的话并不难）。
首先，看起来是不是总觉得和排列组合有千丝万缕的联系？
一般排列组合常用什么方法？
两种：数学/DP。
数学方面这题输入实在太太太太多了，不考虑。
于是乎就只剩下了DP。
状态很好想，自然定义。
转移方程也很好想，无非就是枚举这一行三列依次放什么数。
**接着开始优化，已经瞬间想出三个优化点的dalao可以跳过。**
首先，状态定义。
我们已经知道了每一行三个数的和，因此前多少行总和我们不都是已知了？
所以如果已知$a,b$那$c$不就被唯一确定了？
然后状态珂以压到二维。
类似转移也珂以。
进一步优化：
你会发现每一个转移只与前一行有关。
所以还可以滚动数组~
完整代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e17;
int n,c[109],r[309];
int f[2][129][129];
signed main(){
scanf("%lld%lld%lld%lld",&n,c+1,c+2,c+3);
for(int i=1;i<=n;++i)scanf("%lld",r+i);
//读入
if(accumulate(r+1,r+n+1,-c[1]-c[2]-c[3]))return puts("0"),0;
//特判给定条件矛盾
f[0][0][0]=1;//前0行两列填0（那么第三列也是0）有一种
for(int i=1;i<=n;++i)
for(int j=0;j<=c[1];++j)
for(int k=0;k<=c[2];++k){
f[i&1][j][k]=0;//注意清零！！！
for(int l=0;l<=j&&l<=r[i];++l)
for(int m=0;m<=k&&l+m<=r[i];++m)
f[i&1][j][k]=(f[i&1][j][k]+f[i&1^1][j-l][k-m])%mod;//枚举这一行放了什么
}
printf("%lld\n",f[n&1][c[1]][c[2]]);//输出
return 0;
}
```