专栏首页饶文津的专栏【kAri OJ】621. 廖神的树

【kAri OJ】621. 廖神的树

时间限制 3000 ms 内存限制 65536 KB

题目描述

廖神和男神在植树节的时候准备玩一个奇怪的游戏,他们现在有一个被分割成n*n个格子的矩形土地,他们现在准备往这个地里种树,但这个种树游戏必须满足以下两个要求:

1.每个格子只能是不种树(“0”)或种树(“1”) 2.每行和每列只能种两棵树 现在了不起的廖神种了之前的m行,他邀请男神种完剩下的树。可是男神很懒,这种事他一般都是交给学弟来做,那么聪明的你知道一共有多少种不同的填法吗?

输入格式

第一行是3个整数n,m,mod (2≤n≤500, 0≤m≤n, 2≤mod≤10^9).接下来的m行每行包含n个字符,每行有且仅有2个'1'表示已经种过树了,其余全为'0',表示没有种过树,而给出的每一列上至多有2个1,则廖神会使得他种过的树符合规定. 多组数据, 以EOF结束

输出格式

输出男神能够种果树的方案数 模mod的余数.

输入样例

3 1 1000
011

输出样例

2

分析

这个数据大小就要n2以内的时间复杂度,这样肯定不能搜索。前m行按要求种好了,现在要种的矩形土地里某些列不能种了,某些只能种一棵,剩下的必须种两棵。

我们一行行来种。每种一行,就会出现下面三种状态转移:

i表示能种一棵树的列数,j表示能种两棵树的列数。

1. 选择i列中的两列,i,j 变成 i-2,j。

2. 选择i列和j列的各一列,因为j的某列种了一棵树,这列就变成只能种一棵树的列,所以i,j变成 i,j-1。

3. 选择j中两列,i,j变成i+2,j-2。

dp[k][i][j]表示种完第k行,有i列能种一棵树,j列能种两棵树的方案数。那么就有

dp[k][i][j]+=dp[k-1][i+2][j]*C(i+2,2) 表示k-1行种好后,选择只能种一棵的i+2列里的两列。

dp[k][i][j]+=dp[k-1][i][j+1]*C(i,1)*C(j+1,1) 表示选择i列和j+1列中的各一列。

dp[k][i][j]+=dp[k-1][i-2][j+2]*C(j+2,2) 表示选择j+2列里的两列。

这样最后的dp[n][0][0]就是我们的答案了。

转移时,k在增大。

所以可以这样写循环:

for(k:m+1 to n)

  for(j:0 to b)//j最大就是b了,不可能变大。

    for(i: 0 to n)//为什么是n呢,因为如果先种j列中的列,那么i就在增大,可以大于a,最大到n。

    {...}

能不能减少维数呢?

能种两棵的列往减小或相同的方向转移,即j+1、j+2、j转移到j。

且j相同时,i往小的方向转移,所以我们可以去掉代表第几行的那一维,然后循环这样写:

for(j:b downto 0)

    for(i: n downto 0)

    {...}

一开始dp[a][b](a列能种一棵树,b列能种两棵树。)=1。

代码

#include<cstdio>
#include<cstring>
#define N 550
#define ll long long
int dp[N][N];
int a,b,v[N];
int n,m,mod;
char s[N];
int main()
{
    while(~scanf("%d%d%d",&n,&m,&mod))
    {
        memset(dp,0,sizeof dp);
        memset(v,0,sizeof v);
        b=n;
        a=0;
        for(int i=1; i<=m; i++)
            {
                scanf("%s",s);
                for(int j=0; j<n; j++)
                if(s[j]=='1')
                {
                    v[j]++;
                    if(v[j]==2)
                        a--;
                    else
                    {
                        b--;
                        a++;
                    }
                }
            }
        dp[a][b]=1;
        for(int j=b; j>=0; j--)
            for(int i=n; i>=0; i--)
                if(i!=a||j!=b)
                {
                    if(i>=2)
                        dp[i][j]+=(ll)(j+1)*(j+2)/2 *dp[i-2][j+2]%mod;
                    if(dp[i][j]>=mod)
                        dp[i][j]-=mod;

                    dp[i][j]+=(ll)i*(j+1)*dp[i][j+1]%mod;
                    if(dp[i][j]>=mod)
                        dp[i][j]-=mod;

                    dp[i][j]+=(ll)(i+2)*(i+1)/2 *dp[i+2][j]%mod;
                    if(dp[i][j]>=mod)
                        dp[i][j]-=mod;
                }
        printf("%d\n",dp[0][0]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 3.2】Stringsobits (dp)

    状态转移:dp[i][j]=dp[i-1][j]+dp[i-1][j-1],即第i位放1或者0。

    饶文津
  • 【CodeForces 577B】Modulo Sum

    给你n(1 ≤ n ≤ 106)个数a1..an(0 ≤ ai ≤ 109),再给你m( 2 ≤ m ≤ 103)如果n个数的子集的和可以被m整除,则输出YES...

    饶文津
  • 【HDU 2955】Robberies(DP)

    题意是给你抢劫每个银行可获得的钱m和被抓的概率p,求被抓的概率小于P,最多能抢多少钱。 01背包问题,体积是m,价值是p。 被抓的概率不是简单相加,而应该是

    饶文津
  • Leetcode 91 Decode Ways

    A message containing letters from A-Z is being encoded to numbers using the fol...

    triplebee
  • 递归,递推以及动态规划总结

    在我的映像里面,当初第一次结束DP的时候,总感觉跟递归还是递归好像!以至于我混淆了他们。

    用户7727433
  • Golang Leetcode 823. Binary Trees With Factors.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89378553

    anakinsun
  • LeetCode 1595 Minimum Cost to Connect Two Groups of Points (动态规划)

    题解: 动态规划,用二进制压缩状态,注意分析几种情况,就能推出来正确的状态转移方程。

    ShenduCC
  • 【leetcode刷题】T168-计算各个位数不同的数字个数

    https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

    木又AI帮
  • 01背包和完全背包,一维dp存储区别

          对01背包问题,n个物品背包容量为v,第i个物品的价值为v[i],重量w[i]

    用户2965768
  • Leetcode 120 Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you m...

    triplebee

扫码关注云+社区

领取腾讯云代金券