首页 > 代码库 > SRM 514 DIV1 500pt(DP)

SRM 514 DIV1 500pt(DP)

题目简述

给定一个H×W大小的矩阵,每个格子要么是1~9中的一个数,要么是".",要求你把“.”填成具体的数字(1~9),并且符合以下两个要求:

  • 对于所有的整数r 和 c( 0 <= r <= H-n,0 <= c < W), 使得 F[r][c] + F[r+1][c] + ... + F[r+n-1][c] 是奇数. 
  • 对于所有的整数 r 和c(0 <= r < H,0 <= c <= W-m), 使得 F[r][c] + F[r][c+1] + ... + F[r][c+m-1] 是奇数

题解

    我们可以发现F[r][c]和 F[r+n][c]的奇偶性是一样的,同样F[r][c]和F[c+m]也是同样的奇偶性,那么我们可以把F[r+p*n][c+q*m]的可以放的奇数和偶数的个数统计到odd[r][c]和even[r][c]中,矩阵就压缩成了n*m了!注意如果F[r+p*n][c+q*m]是个确定的数,如果是奇数,那么even[r][c]=0,反之odd[r][c]=0.

  这样问题就转化成了求n×m的矩阵,每行和每列的和都是奇数的方案数!

  接下来我们先预处理出每一行都是奇数和的状态的方案数cnt[i][mask],然后再进行DP,方程是dp[i][mask1^maks2]+=dp[i-1][mask1]*cnt[i][maks2],第i-1行的列状态数是mask1,第i行选取的行状态是mask2,那么形成的列状态就是mask1^maks2,最后的答案就是dp[n][(1<<m)-1],(1<<m)-1恰好表示每一列的状态都是奇数。这道题真是很赞,状态设计好巧妙~~,完全想不到啊!

代码:

 1 typedef long long LL; 2 #define MOD 1000000007 3 LL odd[15][15], even[15][15]; 4 LL dp[15][1 << 12], cnt[15][1 << 12]; 5 class MagicalGirlLevelTwoDivOne 6 { 7 public: 8     int go(int num) 9     {10         int ret = 0;11         while (num)12         {13             ret += num & 1;14             num >>= 1;15         }16         return ret;17     }18     int theCount(vector <string> palette, int n, int m)19     {20         int x = palette.size(), y = palette[0].size();21         for (int i = 0; i < n; i++)22             for (int j = 0; j < m; j++) odd[i][j] = even[i][j] = 1;23         for (int i = 0; i < x; i++)24             for (int j = 0; j < y; j++)25             {26                 if (palette[i][j] == .)27                 {28                     odd[i % n][j % m] *= 5;29                     odd[i % n][j % m] %= MOD;30                     even[i % n][j % m] *= 4;31                     even[i % n][j % m] %= MOD;32                 }33                 else34                 {35                     int num = palette[i][j] - 0;36                     if (num % 2 == 0) odd[i % n][j % m] = 0;37                     else even[i % n][j % m] = 0;38                 }39             }40         memset(cnt, 0, sizeof(cnt));41         for (int i = 0; i < n; i++)42             for (int mask = 0; mask < (1 << m); mask++)43             {44                 int tot = go(mask);45                 if (tot % 2 == 0) continue;46                 cnt[i][mask] = 1;47                 for (int j = 0; j < m; j++)48                 {49                     if (mask & (1 << j))50                         cnt[i][mask] *= odd[i][j];51                     else cnt[i][mask] *= even[i][j];52                     cnt[i][mask] %= MOD;53                 }54             }55         memset(dp, 0, sizeof(dp));56         dp[0][0] = 1;57         for (int i = 1; i <= n; i++)58             for (int mask1 = 0; mask1 < (1 << m); mask1++)59                 for (int mask2 = 0; mask2 < (1 << m); mask2++)60                 {61                     dp[i][mask1 ^ mask2] += (dp[i - 1][mask1] * cnt[i - 1][mask2])%MOD;62                     dp[i][mask1 ^ mask2] %= MOD;63                 }64         return (int)dp[n][(1 << m) - 1];65     }66 };

 

SRM 514 DIV1 500pt(DP)