题目相关
题目描述：
小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2≤N≤10^15)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2≤M≤5,M≤N)个花圃中有不超过K(1<=K<M)个C形的花圃，其余花圃均为P形的花圃。
例如，N=10,M=5,K=3。则
CCPCPPPPCC 是一种不符合规则的花圃；
CCPPPPCPCP 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数Mod 1000000007。请您编写一个程序解决此题。
输入输出格式：
输入格式：
一行，三个数N,M,K。
输出格式：
花园种数Mod 1000000007
输入输出样例：
| 编号 |
输入 |
输出 |
| #1 |
10 5 3 |
458 |
| #2 |
6 2 1 |
18 |
说明：
40%的数据中，N<=20；
60%的数据中，M=2；
80%的数据中，N<=$10^5$。
100%的数据中，N<=$10^{15}$。
博主乱搞
蒟蒻解析1（前80%）：
一定注意这是个环形花园否则就自闭查错吧。
前40%的数据：
应该挺暴力的博主没有尝试。
前60%的数据：
M=2，K=1，即所有的C形都会被分开。可以尝试dp。博主没有尝试。
$f[i][1/0]$代表前i位以及这一位是否是C形，由$f[i-1][1/0]$转移而来。
是不是组合数也可以做博主懒得思考了。。
前80%的数据：
注意到M≤5，说明我们可以进行状态压缩了。
设$f[i][v]$，i代表目前在第几位，v代表前面M位的状态（2进制）。则：
$$f[i][v]=\sum_{u=0}^{2^M-1}{f[i-1][u]*ok[u][v]}$$
u,v分别表示两种状态，$ok[u][v]$当且仅当状态u能一次转移到状态v时成立。转移n次即可，取状态相同结果。
question 1:怎样处理环？
answer 1:我们枚举前M个的位置的情况s,设f[M][s]=1,然后递推到M+N个位置。此时M+N位置其实就相当于第M个位置（因为是个环）。所以只需和初始状况相同即可，即答案贡献为f[M+N][s]。最终结果为所有合法f[M+N][s]的sum。
question 2:怎样处理ok[][]？怎样判断状态是否能转移？
answer 2:我们当然可以在运算中解决。当尝试加入新的一位状态v时，原状态s整体左移一位（移出去的就不管了），然后在空出的一位决定是0还是1。当然为了方便，博主这里采用的是预处理所有情况。所以用了ok[i][j]。
具体代码如下（只有70，开O2就80了，我也不知道为什么。。。）
蒟蒻代码（80%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int p=1e9+7;
int f[2][40];
bool ok[70][70];
bool s_ok[70];
int n,m,k,mx;
bool xx[10];
int tot[10];
ll ans;
void check(){
int tmp1=0,tmp2=0;
for (int i=1;i<=m;++i) tmp1=(tmp1<<1)+((xx[i])?1:0);
for (int i=2;i<=m+1;++i) tmp2=(tmp2<<1)+((xx[i])?1:0);
for (int i=1;i<=m+1;++i) tot[i]=tot[i-1]+((xx[i])?1:0);
for (int i=m;i<=m+1;++i) if (tot[i]-tot[i-m]>k) return;
ok[tmp1][tmp2]=true; s_ok[tmp1]=s_ok[tmp2]=true;
}
void work_ok(int x){
if (x>m+1){
check(); return;
}
xx[x]=true; work_ok(x+1);
xx[x]=false; work_ok(x+1);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
mx=(1<<m)-1;
work_ok(1);
for (int s=0;s<=mx;++s){
if (!s_ok[s]) continue;
int tp=0;
memset(f,0,sizeof(f)); f[tp][s]=1;
for (int i=m+1;i<=n+m;++i){
tp^=1;
for (int j=0;j<=mx;++j){
f[tp][j]=0;
for (int t=0;t<=mx;++t){
if (!ok[j][t]) continue;
f[tp][j]=(f[tp][j]+f[tp^1][t])%p;
}
}
}
ans=(ans+f[tp][s])%p;
}
printf("%lld",ans);
return 0;
}
|
蒟蒻解析2（前100%）：
$10^{15}$的范围让上述算法时空都无法接受。由于是dp，我们可能会联想到矩阵快速幂。所以这个矩阵怎么构造？
我们尝试换一种思路。
设$w[i][u][v]$，表示转移i次，从u状态到v状态的方案数。
当$i=1$时，w[1][u][v]不是1就是0。
当$i=2$时，
$$w[2][u][v]=\sum_{k=0}^{2^M-1}{w[1][u][k]*w[1][k][v]}$$
（是不是和矩阵乘法有相似之处？）
我们不妨可以做的更加普遍一些：
由第x-1次转移到第x状态怎么做？
$$w[x][u][v]=\sum_{k=0}^{2^M-1}{w[x-1][u][k]*w[x-1][k][v]}$$
排除第一位不看，我们可以知道：
每转移一次，就相当于做了一次矩阵乘法。
这样，转移N次得到最终状态的方案数，即w[N][u][v]，就可以由N次矩阵乘法求出。这样就可以愉快地快速幂了。
question 3：所以答案是什么？
answer 3：我们需要的是转移N次后状态与初始状态相同的个数且该状态合法。所以最终答案为:（转移N次后的矩阵为A）
$$Ans=\sum_{i=0}^{2^M-1}{A[i][i]}$$ （一定注意i为合法状态）
question 4：初始矩阵是什么？
answer 4：我们一开始处理的ok[u][v]代表两状态可以一次到达。我们可以把初状态设置为ok[u][v]的矩阵，然后转移N-1次。
然后这道题就可以结束了。
蒟蒻代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int p=1e9+7;
bool s_ok[70];
ll n;
int m,k,mx;
bool xx[10];
int tot[10];
ll trueans;
struct matrix{
ll f[40][40];
void prep(){
memset(f,0,sizeof(f));
}
}u,ans;
matrix operator * (matrix a,matrix b){
matrix tmp; tmp.prep();
for (int i=0;i<=mx;++i){
for (int j=0;j<=mx;++j){
for (int t=0;t<=mx;++t){
tmp.f[i][j]+=a.f[i][t]*b.f[t][j];
tmp.f[i][j]%=p;
}
}
}
return tmp;
}
void check(){
int tmp1=0,tmp2=0;
for (int i=1;i<=m;++i) tmp1=(tmp1<<1)+((xx[i])?1:0);
for (int i=2;i<=m+1;++i) tmp2=(tmp2<<1)+((xx[i])?1:0);
for (int i=1;i<=m+1;++i) tot[i]=tot[i-1]+((xx[i])?1:0);
for (int i=m;i<=m+1;++i) if (tot[i]-tot[i-m]>k) return;
u.f[tmp1][tmp2]=1;
s_ok[tmp1]=s_ok[tmp2]=true;
}
void work_ok(int x){
if (x>m+1){
check(); return;
}
xx[x]=true; work_ok(x+1);
xx[x]=false; work_ok(x+1);
}
int main(){
scanf("%lld%d%d",&n,&m,&k);
mx=(1<<m)-1; u.prep();
work_ok(1); ans=u;
n--;
while (n){
if (n&1) ans=ans*u;
n>>=1; u=u*u;
}
for (int i=0;i<=mx;++i){
if (s_ok[i]){
trueans+=ans.f[i][i];
trueans%=p;
}
}
printf("%lld",trueans);
return 0;
}
|
