洛谷 P1357 花园

题目描述

小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:

【样例输入1】
10 5 3

【样例输入2】
6 2 1

输出样例#1:

【样例输出1】
458

【样例输出2】
18

说明

【数据规模】

40%的数据中,N<=20;

60%的数据中,M=2;

80%的数据中,N<=10^5。

100%的数据中,N<=10^15。

题目分析

八十分做法

前80%的N<=100000,还是可做的,和容易想到用DP搞,因为m<=5,所以我们可以把最后的m盆花进行状压,f[i][j]表示共有i盆花且最后m盆花的状态为j的时候的方案数,那么我们就可以将以个可以转移给j的状态的方案数加给他,即状态转移方程为f[i][j] = Σ f[i-1][k] (k可转移给j),那么问题又来了,题目中说所有的花都是环形,我这样做如何保证所有的方案都是环形的呢.我们可以多次DP
每次DP前将其中一个合法状态赋值k为1,然后从m盆花一直更新到m+n盆花,最后我再将f[m+n][k]加到ans中,这样我就可以保证最后更新出的答案中的方案数都是以最k开始且又以k结束的方案,即组成了一个环.最后的ans即为方案数.为了省时间,我们可以与处理出来哪些方案是合法的,哪些方案能够转移到哪些方案.并用bool记录下来.

以下是八十分代码

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
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long
# define db double
# define mod 1000000007

using namespace std;

LL n,m,k,f[100010][35],ans,t,state[35];
bool ok[35],sure[35][35];

inline void in(R LL &a){
R char c = getchar();R LL x=0,f=1;
while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline int yg(){
in(n),in(m);in(k);
R int tot = (1<<m)-1;
for(R int i=0; i<=tot; ++i)
{
R int d = i;
for(R int j=1,sum=0; j<=m; ++j)
{
if(d&1) sum++;
d>>=1;
if(j==m&&sum<=k) state[++t] = i;
}
}
for(R int i=1; i<=t; ++i)
for(R int j=1; j<=t; ++j){
R int x = state[i],y = state[j];
for(R int p=0; p<m-1; ++p)
{
if(((x>>p)&1) != ((y>>(p+1))&1)) break;
if(p == m-2) sure[i][j] = 1;
}
}

for(R int p=1; p<=t; ++p)
{
memset(f,0,sizeof(f));
f[m][p]=1;
for(R int i=m+1; i<=n+m; ++i)
for(R int j=1; j<=t; ++j)
for(R int k=1; k<=t; ++k)
if(sure[k][j])
f[i][j]=(f[i-1][k]+f[i][j])%mod;
ans = (ans+f[m+n][p])%mod;
}
cout << ans;
}
int youngsc = yg();
int main(){;}

100分做法

其实我们会发现,对于一个合法状态,更新它的合法状态始终是不变的,并且总会更新N次,也就是说对于每一次转移,都相当于给原数组乘以了一个矩阵,并且很显然这个矩阵是不变的,而且它就是当初我们处露出来的表示转移关系的那个bool数组,也就是上边代码中的sure,既然这样,那我们的f[i][j]中的第一维就没有任何意义了,我们可以将它扔掉,变成一个一维数组,当我们试图去写最终的f数组与sure相乘时你又会发现,因为f数组中只有当前枚举的合法状态是1,其余均是0,并且最重要的也是f数组中的k,所以按照矩阵乘法的原则,只需在最终的答案中加上sure[k][k]即可,
因为对于不同的k最终的sure数组是不变的,所以最终的答案就是sure矩阵对角线的和。

AC代码

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
69
70
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long
# define db double
# define mod 1000000007LL

using namespace std;

LL n,m,k;
int f[64],anss,t;
int state[64],sure[64][64],ans[64][64];
bool ok[64];

inline void in(R LL &a){
R char c = getchar();R LL x=0,f=1;
while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline void powe(R int a[64][64],R int b[64][64]){
R int d[64][64] = {0};
for(R int i=1; i<=t; ++i)
for(R int j=1; j<=t; ++j)
for(R int k=1; k<=t; ++k)
d[i][j] = (d[i][j]*1LL+(1LL*a[i][k]*b[k][j])%mod)%mod;
memcpy(a,d,sizeof(d));
}

inline int yg(){
in(n),in(m);in(k);
R int tot = (1<<m)-1;
for(R int i=0; i<=tot; ++i)
{
R int d = i;
for(R int j=1,sum=0; j<=m; ++j)
{
if(d&1) sum++;
d>>=1;
if(j==m&&sum<=k) state[++t] = i;
}
}
for(R int i=1; i<=t; ++i) ans[i][i] = 1;
for(R int i=1; i<=t; ++i)
for(R int j=1; j<=t; ++j){
R int x = state[i],y = state[j];
for(R int p=0; p<m-1; ++p)
{
if(((x>>p)&1) != ((y>>(p+1))&1)) break;
if(p == m-2) sure[i][j] = 1;
}
}

R LL r = n;
while(r)
{
if(r&1LL) powe(ans,sure);
if(r>1LL) powe(sure,sure);
r>>=1LL;
}

for(R int p=1; p<=t; ++p) anss = (anss*1LL+ans[p][p]*1LL)%mod;
cout << anss;
}
int youngsc = yg();
int main(){;}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
    1. 1.0.1. 输入输出格式
      1. 1.0.1.0.1. 输入格式:
      2. 1.0.1.0.2. 输出格式:
  2. 1.0.2. 输入输出样例
    1. 1.0.2.0.1. 输入样例#1:
    2. 1.0.2.0.2. 输出样例#1:
  • 1.0.3. 说明
  • 1.1. 题目分析
    1. 1.1.1. 八十分做法
    2. 1.1.2. 以下是八十分代码
    3. 1.1.3. 100分做法
    4. 1.1.4. AC代码
  • ,