BZOJ4000 [TJOI2015]棋盘-白红宇

BZOJ4000 [TJOI2015]棋盘

阅读量：5046 次

发布时间：2019-06-12

本文共 3229 字，大约阅读时间需要 10 分钟。

首先是状态压缩DP。。。

然后我们发现转移都是一样的。。。可以矩阵优化。。。

于是做完啦QAQQQ

题目读不懂？恩多读几遍就读懂了，诶诶诶！别打我呀！

1 /**************************************************************  2     Problem: 4000  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:208 ms  7     Memory:920 kb  8 ****************************************************************/  9   10 #include 
      
        11 #include 
       
         12 #include 
        
          13   14 using namespace std; 15 typedef unsigned int uint; 16 const int N = 75; 17   18 inline int read(); 19   20 int n, m, p, K, Mx; 21 int a[N][N], f[N]; 22 vector 
         
           mp[3]; 23 uint ans; 24   25 struct mat { 26     uint x[64][64]; 27     mat() { 28         memset(x, 0, sizeof(x)); 29     } 30     inline void one() { 31         static int i; 32         *this = mat(); 33         for (i = 0; i < Mx; ++i) x[i][i] = 1; 34     } 35     inline uint* operator [] (int t) { 36         return x[t]; 37     } 38       39     inline mat operator * (const mat &m) const { 40         static mat res; 41         static int i, j, k; 42         res = mat(); 43         for (i = 0; i < Mx; ++i) 44             for (j = 0; j < Mx; ++j) 45                 for (k = 0; k < Mx; ++k) 46                     res[i][j] += x[i][k] * m.x[k][j]; 47         return res; 48     }    49 } A; 50   51 inline mat pow(const mat& m, int y) { 52     static mat x, res; 53     x = m, res.one(); 54     int i, j; 55     while (y) { 56         if (y & 1) res = res * x; 57         x = x * x, y >>= 1; 58     } 59     return res; 60 } 61   62 inline bool in(int x) { 63     return 0 <= x && x < m; 64 } 65   66 inline bool check(int s1, int s2) { 67     static int i, j, t; 68     for (i = 0; i < m; ++i) if ((s1 >> i) & 1) { 69         for (j = 0; j < mp[1].size(); ++j) 70             if (in(t = i + mp[1][j]) && ((s1 >> t) & 1)) return 0; 71         for (j = 0; j < mp[2].size(); ++j) 72             if (in(t = i + mp[2][j]) && ((s2 >> t) & 1)) return 0; 73     } 74     for (i = 0; i < m; ++i) if ((s2 >> i) & 1) { 75         for (j = 0; j < mp[1].size(); ++j) 76             if (in(t = i + mp[1][j]) && ((s2 >> t) & 1)) return 0; 77         for (j = 0; j < mp[0].size(); ++j) 78             if (in(t = i + mp[0][j]) && ((s1 >> t) & 1)) return 0; 79     } 80     return 1; 81 } 82   83 int main() { 84     int i, j; 85     n = read(), m = read(), p = read(), K = read(), Mx = 1 << m; 86     for (i = 0; i < 3; ++i) 87         for (j = 0; j < p; ++j) 88             if (read() && !(i == 1 && j == K)) mp[i].push_back(j - K); 89     for (i = 0; i < Mx; ++i) 90         for (j = 0; j < Mx; ++j) A[i][j] = check(i, j); 91     for (i = 0; i < Mx; ++i) f[i] = bool(A[0][i]); 92     A = pow(A, n); 93     for (i = 0; i < Mx; ++i) ans += f[i] * A[i][0]; 94     printf("%u\n", ans);     95     return 0; 96 } 97   98 inline int read() { 99     static int x;100     static char ch;101     x = 0, ch = getchar();102     while (ch < '0' || '9' < ch)103         ch = getchar();104     while ('0' <= ch && ch <= '9') {105         x = x * 10 + ch - '0';106         ch = getchar();107     }108     return x;109 }