codeforces 489F Special Matrices（DP）

最新推荐文章于 2020-12-26 20:31:58 发布

tsxhl111

最新推荐文章于 2020-12-26 20:31:58 发布

阅读量1.8k

点赞数

分类专栏： DP

本文链接：https://blog.csdn.net/tsxhl111/article/details/41281983

版权

DP 专栏收录该内容

4 篇文章

订阅专栏

传送门：点击打开链接

题目大意：

给定一个n*n的01矩阵的前m行，要求求出有多少种构造方案使得：每一行，每一列的1的个数都是2

解题思路：

既然已经给定了前m行，那么就相当于告诉了我们有哪几列，还能放2个1,1个1，和不能再放1了。

注意到，这个时候列之间是可以交换的，那么就可以做了。

定义dp[i][j][k]表示在第i行剩j个位置可以放2个1，剩k个位置可以放1个1。

因为下一行一定要放2个1，那么就有3种转移状态：

1：全部选的是放2个的。那么就转移到了dp[i+1][j-2][k+2]状态。（因为剩可以放1个种类多了2个）

2：全部选的是放1个的。那么就转移到了dp[i+1][j][k-2]状态。

3：选一个j，选一个k。那么就转移到了dp[i+1][j-1][k]状态。

注意一下常数优化，不然会T。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
LL dp[2][505][505];


int main()
{
    LL n,m,MOD;
    scanf("%lld %lld %lld",&n,&m,&MOD);
    memset(dp,0,sizeof dp);
    LL a[505];
    for(int i = 1;i <= n;i++) a[i] = 2;
    for(int i = 1;i <= m;i++)
    {
        char s[505];
        scanf("%s",s);
        for(int j = 0;j < n;j++)
            if(s[j] == '1')  a[j+1]--;
    }
    int x = 0,y = 0;
    for(int i = 1;i <= n;i++) if(a[i] == 2)x++;else if(a[i] == 1) y++;
    int cur = 0;
    dp[cur][x][y] = 1;
    for(int i = m+1;i <= n;i++)
    {
        cur = cur^1;
        memset(dp[cur],0,sizeof dp[cur]);
        for(int j = 0;j <= n;j++)
        {
            for(int k = 0;k <= n;k++)
            {
                if(!dp[cur^1][j][k]) continue;//优化，没有会T
                if(j >= 2)
                    dp[cur][j-2][k+2] = (dp[cur][j-2][k+2] + dp[cur^1][j][k]*(j-1)*j/2)%MOD;
                if(k >= 2)
                    dp[cur][j][k-2] = (dp[cur][j][k-2] + dp[cur^1][j][k]*(k-1)*k/2)%MOD;
                if(j >= 1 && k >= 1)
                    dp[cur][j-1][k] = (dp[cur][j-1][k] + dp[cur^1][j][k]*j*k)%MOD;
            }
        }

    }
    printf("%lld\n",dp[cur][0][0]);
    return 0;
}