Just OI-ACM

矩阵的个数

 
  • Apr 13, 2019

Problem

Source: CQOI 2008

Description

给出一个 $N$ 行 $3$ 列非负整数矩阵的各行各列之和，统计有多少个矩阵满足此条件。输出答案模 $10^{17}$ 的值。

Input

第一行包含四个正整数 $N, c_1, c_2, c_3$，即行数与三列之和。第二行包含 $N$ 个正整数，即各行三个数之和。每行每列之和均不超过 125。

Output

仅一个数，满足条件的矩阵个数模 $10^{17}$ 的值。

Sample Input

3 2 3 4
1 2 6

Sample Output

17

 

Solution

如果前两列的都满足条件，那么第三列的和也一定满足条件，所以动归时只需要考虑前两列。

$f(k,x,y)$：前 $k$ 行，满足第一列和为 $c_1$，第二列和为 $c_2$ 的矩阵个数

状态转移方程：

\[f(k,x,y) += f(k-1,x-i,y-j)\]

Code

Github (C++)

#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

const ll Mod = 100000000000000000LL;
ll f[505][130][130];
int a[205];
int n, c1, c2, c3;

void Dp() {
    f[0][0][0] = 1;
    for(int k = 1; k <= n; k++)
        for(int x = 0; x <= c1; x++)
            for(int y = 0; y <= c2; y++)
                for(int i = 0; i <= min(x, a[k]); i++)
                    for(int j = 0; j <= min(y, a[k] - i); j++)
                        f[k][x][y] = (f[k][x][y] + f[k - 1][x - i][y - j]) % Mod;

   printf("%lld\n", f[n][c1][c2]);
}

int main() {
  scanf("%d", &n);
  scanf("%d%d%d", &c1, &c2, &c3);
  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

  Dp();

  return 0;
}
Search