题目id:2213
题意
给定一个 n\times3 的矩阵的各行各列之和，求满足条件的矩阵的个数。
Solution
计数题，考虑朴素 dp，定义 f_{i,a,b,c} 为当前枚举到第 i 行，每列之和分别为 a ， b ， c 时的方案数。枚举当前列所填数，令其分别为 now_1 ， now_2 ， now_3 则有转移方程：
\large{f_{i,a,b,c}\gets f_{i-1,a-now_1,b-now_2,c-now_3}}
由于各行，列之和均小于等于125，故每行之和大约在 \frac{125\times 3}{n} 左右，故朴素 dp 复杂度约为 \mathcal{O}(\dfrac{125^6\times9}{n^2}) ，无法在时限内通过本题。故考虑优化。
发现当 a ， b 确定时， c 也确定，故由此可通过前缀和将第四位优化掉，$now_1$，$now_2$，$now_3$ 同理。故当满足 \sum^{i}_{k=1}sum_k-a-b \ge 0 且 sum_i-now_1-now_2 \geq 0 时有转移方程：
\large{f_{i,a,b}\gets f_{i-1,a-now_1,b-now_2}}
最坏时间复杂度约为 \mathcal{O}(\dfrac{3\times125^4}{n}) ，可以通过本题。
code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=getchar();
while(isalnum(ch)) res=res*10+ch-'0',ch=getchar();
return res*flag;
}
int val[210];
long long dp[210][210][210];
int main(int argc,const char *argv[])
{
int n=read();
int s1=read(),s2=read(),s3=read();
for(int i=1;i<=n;i++)
val[i]=read();
dp[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int n1=0;n1<=s1;n1++)
for(int n2=0;n2<=s2;n2++)
for(int d1=0;d1<=n1&&d1<=val[i];d1++)
for(int d2=0;d2<=n2&&d1+d2<=val[i];d2++)
dp[i][n1][n2]=(dp[i][n1][n2]+dp[i-1][n1-d1][n2-d2])%(long long)1e17;
printf("%lld",dp[n][s1][s2]);
return 0;
}
写在最后
三年 OI 一场空，不开 long long 见祖宗