洛谷P1357 花园

发表于 | 分类于
字数统计: 502 | 阅读时长 ≈ 3

观察到m 比较小，考虑状压m
对于当前状态s
当s‘ 去掉末尾位和s 去掉开头位相等，且s‘ 中个数<=k

然而问题没有这么简单，花园是个环
设开头m 个状态为s ，则 为以s 开头的答案
因此枚举开头所有状态即可，这样就有80分了

对于最后20分
首先观察转移
设当s 可以转移到s’ 时，

与矩阵乘法一致
因此

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
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int N=8,mod=1e9+7;
LL n,m,k,r,num[1<<N];
namespace Matrix
{
    struct mtrx{LL w[1<<N][1<<N];} f;
    void fill(mtrx &M,LL x)
    {
        for(int i=0;i<(1<<m);i++)
            for(int j=0;j<(1<<m);j++) M.w[i][j]=x;
    }
    void init(mtrx &M)
    {
        fill(M,0);
        for(int i=0;i<(1<<m);i++) M.w[i][i]=1;
    }
    void cpy(mtrx &M,mtrx &C)
    {
        for(int i=0;i<(1<<m);i++)
            for(int j=0;j<(1<<m);j++) M.w[i][j]=C.w[i][j];
    }
    void mul(mtrx &M,mtrx C,int mod)
    {
        mtrx ret;
        fill(ret,0);
        for(int i=0;i<(1<<m);i++)
            for(int j=0;j<(1<<m);j++)
                for(int k=0;k<(1<<m);k++)
                    ret.w[i][j]=(ret.w[i][j]+M.w[i][k]*C.w[k][j])%mod;
        cpy(M,ret);
    }
    void pow(mtrx &M,LL x,int mod)
    {
        mtrx ret;
        init(ret);
        for(;x;x>>=1)
        {
            if (x&1) mul(ret,M,mod);
            mul(M,M,mod);
        }
        cpy(M,ret);
    }
};
using namespace Matrix;
void init()
{
    fill(f,0);
    for(int i=0;i<(1<<m);i++) if (num[i]<=k)
        for(int j=0;j<(1<<m);j++) if (num[j]<=k)
            if ((i&((1<<(m-1))-1))==(j>>1)) f.w[i][j]=1;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int s=0;s<(1<<m);s++)
        for(int i=1;i<=m;i++)
            num[s]+=(s>>(i-1))&1;
    init();
    pow(f,n,mod);
    LL ans=0;
    for(int s=0;s<(1<<m);s++) 
        if (num[s]<=k) 
            ans=(ans+f.w[s][s])%mod;
    printf("%lld\n",ans);
    return 0;
}