题目传送门

题目分析

80pts

前$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
61
# 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(){;}

AC

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

代码

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(){;}