题解 P5343 【【XR-1】分块】

· · 题解

比赛时忘记去重没AC。。。

60分:根据题意分析，先把两人要求的分块大小公共部分处理出来。 对于当前长度，枚举它可以是由哪些长度转移过来即可。

比如说样例1，公共部分是1,2，序列长度为4。长度为4的序列可以由长度为2的序列再填一个长度为2的块，或者长度为3的序列填一个长度为1的块组成。如果设长度为i的方案数为f[i]，那么f[4]=f[2]+f[3]。显然是个递推，边界f[0]=1(长度为0只能啥块都不用)，对于每个长度i，枚举块长j，f[i]+=f[i-j]。复杂度O(nx);

100分：发现上边的式子是一个线性齐次递推式（放弃解释概念），说白了就是跟斐波那契数列有点像，所以可以矩阵快速幂。 复杂度O(x^3logn)。

最后奉上代码。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
long long n;
int pr,nf,tot=0;
int a[150],b[150];
int solve[150],vis[150];
long long f[150];
struct node{
    long long sq[105][105];
}power,ans;
//a[i]=sum(a[i]-solve[j])
node add(node x,node y){
    node c;
    memset(c.sq,0,sizeof(c.sq));
    for(int i=1;i<=solve[tot];i++){
        for(int j=1;j<=solve[tot];j++){
            for(int k=1;k<=solve[tot];k++){
                c.sq[i][j]=(c.sq[i][j]+(x.sq[i][k]*y.sq[k][j])%mod)%mod;
            }
        }
    }
    return c;
}
int main(){
    memset(f,0,sizeof(f));
    scanf("%lld",&n);
    scanf("%d",&pr);
    for(int i=1;i<=pr;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&nf);
    for(int i=1;i<=nf;i++){
        scanf("%d",&b[i]);
    }
    sort(a+1,a+pr+1);
    sort(b+1,b+nf+1);
    int cnta=1,cntb=1;
    memset(vis,0,sizeof(vis));
    while(cnta<=pr&&cntb<=nf){
        if(a[cnta]==b[cntb]){
            if(!vis[a[cnta]])solve[++tot]=a[cnta];
            vis[a[cnta]]=1;
            cnta++;
            cntb++;
        }
        else if(a[cnta]<b[cntb]){
            cnta++;
        }
        else cntb++;
    }
    f[0]=1;
    for(int i=1;i<=solve[tot];i++){
        for(int j=1;j<=tot;j++){
            if(i-solve[j]>=0)f[i]=(f[i]+f[i-solve[j]])%mod;
        }
    }
    memset(ans.sq,0,sizeof(ans.sq));
    for(int i=1;i<=solve[tot];i++){
        ans.sq[i][i]=1;
    }
    memset(power.sq,0,sizeof(power.sq));
    for(int i=2;i<=solve[tot];i++){
        power.sq[i][i-1]=1;
    }
    for(int i=1;i<=tot;i++){
        power.sq[solve[tot]+1-solve[i]][solve[tot]]=1;
    }
    long long p=n-solve[tot];
    while(p){
        if(p&1){
            ans=add(ans,power);
        }
        power=add(power,power);
        p>>=1;
    }
    long long cnt=0;
    for(int i=1;i<=solve[tot];i++){
        cnt=(cnt+f[i]*(ans.sq[i][solve[tot]])%mod)%mod;
    }
    printf("%lld\n",cnt);
    return 0;
}

常数写的有点大，最大的一个点跑了900+ms。。。