Problem A 游戏
有$n (1 \leq n \leq 5)$个硬币初始以"0"(正面)，"1"(反面) $m (1 \leq m \leq m)$种操作，每一种操作可以将一些硬币进行翻转。
但是有$ k (0 \leq k < \frac{(m-1)\times m}{2}$) 组限制，每组限制描述$A$操作和$B$操作互不能连续进行。
已知翻转游戏进行$T$轮，求$T$轮之后，硬币全部翻转成反面朝上的方案数。
对于100%的数据 $1 \leq T \leq 10^5$
对于真正的100%的数据 $1 \leq T \leq 10^9 $
Sol : 对于100%的数据发现T的值比较小，暴力状压DP即可。
设 $f_{i,j,k}$ 表示当前是第 $i$ 轮末，当前硬币的状态是 $j$ ,上一次转移而来的翻转操作的编号为 $k$。
转移方程为$f_{i,j,k} = \sum\limits_{j‘=0,k‘=1 }^{j‘ \leq 2^n-1 , k‘ \leq m} f_{i-1,j‘,k‘}$，
其中限制是$j‘$可以通过操作$k$变为$j$,并且操作$k$和操作$k‘$可以连续进行。
所以，这种算法的时间复杂度是$O(T\times 2^n m n )$，可以AC。
# pragma GCC optimize(3) # include <bits/stdc++.h> using namespace std; const int mo=1e9+7; int a[6],n,m,k,T,tmp[6]; vector<int>v[6]; int f[1000001][32][6]; int main() { scanf("%d%d%d",&n,&m,&k); int start=0; for (int i=1;i<=n;i++) { int t; scanf("%d",&t); start=(start<<1)+t; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) v[i].push_back(j); for (int i=1;i<=m;i++) { int t; scanf("%d",&t); memset(tmp,0,sizeof(tmp)); for (int j=1;j<=t;j++) { int o; scanf("%d",&o); tmp[o]=1;} int rr=0; for (int j=1;j<=n;j++) rr=(rr<<1)+tmp[j]; a[i]=rr; } for (int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); for (int j=0;j<v[x].size();j++) if (v[x][j]==y) v[x].erase(v[x].begin()+j); for (int j=0;j<v[y].size();j++) if (v[y][j]==x) v[y].erase(v[y].begin()+j); } memset(f,0,sizeof(f)); for (int i=1;i<=m;i++) { f[1][start xor a[i]][i]=1; } scanf("%d",&T); for (int i=2;i<=T;i++) for (int j=0;j<=(1<<n)-1;j++) for (int k=1;k<=m;k++) for (int t=0;t<v[k].size();t++) { int w=v[k][t]; f[i][j][k]=(f[i-1][j^a[k]][w]+f[i][j][k])%mo; } int ans=0; for (int i=1;i<=m;i++) ans=(ans+f[T][(1<<n)-1][i])%mo; printf("%d\n",ans); return 0; }
而对于真正100%的数据则要使用矩阵加速DP，考虑到状态$(j‘,k‘)$可以变成$(j,k)$的条件是$j‘$可以通过操作$k$变为$j$,并且操作$k$和操作$k‘$可以连续进行。
所以我们可以预处理出一个矩阵表示从某一个状态的二元组到另外一个状态的二元组的转移是否可行，如果可行置为1，不可行置为0.
如何在普通的矩阵中表示一个转移的二元组呢？可以Hash一下，把二元组$ (j,k) $表示成$ j\times m + k$即可完成转移。
实现方面，先预处理出T=1时的情况（不存在转移的合法性）作为初始矩阵，然后若转移$(j‘,k‘)$到$(j,k)$合法，那么就将$A[j‘m+k‘][jm+k]$置为1，否则置为0.
然后对于矩阵A计算$A^{T-1}$表示，这个相同的转移方式一共进行T-1次，获得的矩阵再乘以初始矩阵就是最终的答案矩阵$Ans$了，
最终的答案只需对$Ans$矩阵每个元素求和即可。
复杂度是$O(log_2 T (2^n m + k)^3 )$足以通过$T\leq 10^9$的数据。
#include <fstream> #include <algorithm> using namespace std; ifstream in("game.in"); ofstream out("game.out"); const int N = 200; const long long P = 1000000007; const int M = 6; int operatorlist[M]; int n, m, t, s; int start_bit = 0; int ban[M][M]; long long tmp[N][N]; long long result[N][N]; void matrix_multiplication(int n, long long A[N][N], long long B[N][N]) { int C[N][N]; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { C[i][j] = 0; } for (int i=0; i<n; i++) for (int j=0; j<n; j++) for (int k=0; k<n; k++) { C[i][j] =(C[i][j]+(A[i][k]*B[k][j] % P))%P; } for (int i=0; i<n; i++) for (int j=0; j<n; j++) { A[i][j] = C[i][j]; } } void matrix_addition(int n, long long A[N][N], long long B[N][N]) { for (int i=0; i<n; i++) for (int j=0; j<n; j++) { A[i][j]=(A[i][j]+B[i][j]) % P; } } void input() { in>>n>>m>>t; for (int i=0; i<n; i++) { int x; in>>x; start_bit = (start_bit<<1)+x; } for (int i=0; i<m; i++) { int k, op = 0; in>>k; for (int j=0; j<k; j++) { int x; in>>x; op += 1<<(n-x); } operatorlist[i+1] = op; } for (int i=0; i<t; i++) { int x, y; in>>x>>y; ban[x][y] = 1; ban[y][x] = 1; } in>>s; } void work() { for (int i=0; i<(1<<n); i++) for (int j=0; j<m; j++) for (int k=0; k<m; k++) if (ban[j+1][k+1]!=1) { int next_i = i^operatorlist[k+1]; tmp[i*m+j][next_i*m+k] = 1; } int nn = (1<<n)*m; bool first = true; s-=1; while (s>0) { if (s&1) { if (first){ matrix_addition(nn, result, tmp); first = false; }else { matrix_multiplication(nn, result, tmp); } } matrix_multiplication(nn, tmp, tmp); s>>=1; } } void output() { long long ans =0; for (int i=0; i<m; i++) for (int j=0; j<m; j++) { ans = (ans + result[(start_bit^operatorlist[j+1])*m+j][((1<<n)-1)*m+i]) % P; } out<<ans<<endl; in.close(); out.close(); } int main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); input(); work(); output(); }
原文：https://www.cnblogs.com/ljc20020730/p/11164515.html
