CF489F [Special Matrices] 题解

前言

难度:3星

做法:dp + 滚动数组优化

题目翻译（摘选自luogu（我翻译的，引用应该没有问题吧.....））：

简化题意：

给定一个的矩阵的前行，求满足每行以及每列的和为2的01矩阵的数量

思路

(这里提供的是 O()) 的做法。

观察到数据范围，发现不大像数学题，但是貌似也不是模拟题，看到方案数，就想到了 。

考虑怎么去除掉给出的前 行的影响。实际上这 行的用处不是很大，只是限制了某些列上填入的一的个数。

然后很轻松的可以得到，哪些列只能填入一个 以及哪一些可以填两个。

这样就把 的影响去除了。

如何设立状态?

分析：

因为并不需要知道哪一些位置填了 ，实际上只要记录一下 哪一些列可以填一个 ，哪一些列可以填两个 ，以及当前行填多少个， 但是因为当前行填的又必须是两个，所以可以不用记录行有多少个。

得出做法:

不妨设立状态：

为填到第 行，还剩下 可以填入一个 ， 还有 列可以填两个 。

这样子貌似会爆空间。想到每次只会用到 以及 ，不妨使用滚动数组的技巧。

设立状态:

表示还剩下 行可以填一个1，还有 行可以填两个。

另外初始边界为：

(,分别表示在被 行已知矩阵的情况下只能填一个的列的数量以及只能填两个的列的数量)

怎么转移？

实际上根据设立的状态，很容易想到：

• 当前行选择填入两个的两列 一个为可以填两个的列，一个为可以填 1 个1的列

• 当前行选择填入两个的列都为可以填两个的列

• 当前行选择填入两个的列都为可以填一个的列

同时需要注意，那一些 要填 2 两个 1 的列填入一个 1 后就转化为了要填一个1的列，这个在dp方程中是有体现的。

同时任意选两个的话，根据乘法原理推推式子转移即可。

以上三种情况对应的状态转移方程分别为:

• += ^

• += ^ *

• += ^ *

( ^ 即是滚动数组的技巧,^表示异或)

关于方程的解释：

第一个方程：只有 是因为在某一可填入 2 个 1 的 列 填入一个1后，这个可以填两个1的列就变成了只能填 1 个 1 的列，因此 的 -1 就被抵消掉了。同时不难发现，在 列里任选一个，在 列中任选一个，方案数目是 种的，因此得到这个状态转移方程。

第二个方程： 是因为我们假设填入的两个 1 都位于可以填入 1 个 1 的列，那么方案数就是 ，也就是从 列中任选两个的方案数，用组合的知识算一算就会得到总方案数就是 。

第三个方程: 并且 就是说，选择的两列都是能填入 2 个 1 的列，这样子的话，这两个可以填两个1的列就变成了只能填 1 个 1 的列，因此 , ，然后总方案数就是 ，也就是 。

运算过程记得取模，虽然翻译温馨提示了一波 可能不是质数，但是不影响取模，因为没有除法（大雾）

最后的答案即为:

具体的看一看代码：

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 505;

int n,m,Mod,Cnt1 = 0, Cnt2 = 0;
int L[MAXN];
char a[MAXN];
int dp[2][MAXN][MAXN]; //第一维是滚动数组，第二维表示有 i 列能填入 1 个 1，第三维表示有 j 列能填入两个 1

int C(int x)
{
    return x * (x - 1) / 2;
}

void Clean(int now)//对于DP数组进行清零
{
    for(int j = 0 ; j <= Cnt1 ; j ++)
        for(int k = 0 ; k <= Cnt2 ; k ++)
    dp[now][j][k] = 0;//一定要注意重置，不然会wa!
    return ;
}

void DP(int now)//进行状态转移
{
     for(int j = 0 ; j <= n ; j ++)
    {
        for(int k = 0 ; k <= n ; k ++)
        {
            if( dp[now ^ 1][j][k] == 0)continue;//肯定不会做出贡献，没必要转移，防止TLE
            if(j >= 1 && k >= 1)//对应方程1
            {
               dp[now][j][k - 1] += (dp[now ^ 1ll][j][k] * j * k )% Mod, 
               dp[now][j][k - 1] %= Mod;
            }
            if(j >= 2)//对应方程2
            {
                dp[now][j - 2][k] += (dp[now ^ 1ll][j][k] * C(j)) % Mod;
                dp[now][j - 2][k] %= Mod;
            }
            if(k >= 2)//对应方程3
            {
                dp[now][j + 2][k - 2] += (dp[now ^ 1ll][j][k] * C(k)) % Mod;
                dp[now][j + 2][k - 2] %= Mod;
            }
       }
    }
    //状态转移方程的解释见上面的题解处
    return ;
}

signed main()
{
    cin >> n >> m >> Mod;
    for(int i = 1 ; i <= n ; i ++)L[i] = 2;//一开始假定全部都只能填入两个1
    for(int i = 1 ; i <= m ; i ++)
    {
        cin >> a + 1;
        for(int j = 1 ; j <= n ; j ++)
        if(a[j] == '1')L[j] --;
    }

    for(int i = 1 ; i <= n ; i ++)
    {//统计有多少列只能填一个1以及哪一些列只能填两个1
        if(L[i] == 1)Cnt1 ++;//Cnt1 就表示只能填入一个1的列
        else if(L[i] == 2)Cnt2 ++;//Cnt2 表示 能填入两个1 的列
    }
    dp[0][Cnt1][Cnt2] = 1;//初始化边界
    int now = 0;
    for(int i = m + 1 ; i <= n ; i ++)
    {
        now = (now ^ 1ll);
        Clean(now);
        DP(now);
    }
    cout << dp[now][0][0] % Mod;
    return 0;
}

后话

这个做法感觉有点卡，写完了以后看了看当时比赛的题解，貌似有O()的解法，有兴趣的同学可以自己百度一下呀。这个题目还是挺好的！