NOIP模拟赛 czy的后宫

【题目描述】

czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。

【输入格式】

输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。

【输出格式】

输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。

【样例输入】

2 2

【样例输出】

【样例说明】

七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。

【数据范围】

20%的数据，1＜n≤5,0＜m≤10。

60%的数据，1＜n≤200,0＜m≤100。

100%的数据，1＜n≤1000000000，0＜m≤100。

注：此题时限1.5s是因为本评测机跑太慢，大家正常做

但写的太丑可能T一俩个点

前辈都忙着开后宫了，就我这个苦逼在弱校挣扎。。。

F[i][j]={F[i-1][k]} i表示由i个妹子组成，j代表以j结尾

用异或状态压缩

60分：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int mod=1000000007;
 5 
 6 int n,m,ans,p=0;
 7 int F[2][101];
 8 bool D[101][101];
 9 char s[255];
10 
11 int main()
12 {
13     cin>>n>>m;
14     for(int i=1;i<=m;i++)
15     {
16         scanf("%s",s+1);
17         for(int j=1;j<=m;j++)
18             D[i][j]=s[j]-'0';
19     }
20     for(int i=0;i<=m;i++) F[0][i]=1;
21     for(int i=2;i<=n;i++)
22     {
23         p^=1;
24         for(int j=0;j<=m;j++)
25         {
26             F[p][j]=0;
27             for(int k=0;k<=m;k++)
28                 if(!D[j][k])
29                     F[p][j]=(F[p][j]+F[p^1][k])%mod;
30         }
31     }
32     for(int i=0;i<=m;i++)
33         ans=(ans+F[p][i])%mod;
34     cout<<ans<<endl;
35     return 0;
36 }

100分要用矩阵乘法配合图论来做

f[i][k]表示从i到k的路径条数，即以第i盆花开始，第k盆花结束的摆法有多少种

那么f[i][k]=Σ(f[i][j]*f[j][k])

即f=f*gⁿ

配合快速幂

最后ans=Σ(f[i][0])

 1 #define LL long long
 2 
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 const int MAXN=105;
 8 const int mod=1000000007;
 9 
10 struct MAT
11 {
12     LL mat[MAXN][MAXN];
13 }f,g;
14 LL n,m,ans;
15 char ch[255];
16 
17 MAT mult(MAT a,MAT b)
18 {
19     MAT t;
20     memset(t.mat,0,sizeof(t.mat));
21     for(int i=0;i<=m;i++)
22         for(int j=0;j<=m;j++)
23             if(a.mat[i][j])
24                 for(int k=0;k<=m;k++)
25                     t.mat[i][k]=(t.mat[i][k]+a.mat[i][j]*b.mat[j][k])%mod;
26     return t;
27 }
28 
29 void modexp(int b)
30 {
31     while(b)
32     {
33         if(b&1) f=mult(f,g);
34         g=mult(g,g);
35         b>>=1;
36     }
37 }
38 
39 int main()
40 {
41     cin>>n>>m;
42     for(int i=1;i<=m;i++)
43     {
44         scanf("%s",ch+1);
45         for(int j=1;j<=m;j++)
46             if(ch[j]=='0') g.mat[i][j]=1;
47     }
48     for(int i=0;i<=m;i++)
49     {
50         g.mat[0][i]=g.mat[i][0]=1;
51         f.mat[i][i]=1;
52     }
53     modexp(n);
54     for(int i=0;i<=m;i++)
55         ans=(ans+f.mat[i][0])%mod;
56     cout<<ans<<endl;
57     return 0;
58 }