jzoj5836 Sequence 矩阵乘法+快速幂

Description

---

Solution

---

最后10min写出的24‘暴力还是很稳的，这个杯具提醒我们以后要提前看比赛结束时间和提前打暴力

考虑计数，如果不算那m个的话可以设f[i]表示以第i位为结尾的序列方案数，设last[i]为上一个a[i]的位置，那么有fi=∑last[i]≤j≤i−1fj$f_i=\sum _{last[i]\le j\le i-1}{f}_j$，这个可以前缀和一下做

现在我们需要加上m个数字。考虑要方案数最大，因此我们每次加入last最小的数字，使得统计到f中的这一项尽可能大

然后就非常套路了。m很大k很小，我们设一个k+1维向量保存前缀和来做矩阵乘法，搞一搞转移矩阵快速幂就可以了

改完题回头看会发现这么多的部分分并没有被我拿满。感觉这几天做的比赛都比较ok，但是由于各种原因不能拿到比较好看的分数，我果然还是太鶸了

Code

---

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st,_=ed;i<=_;++i)
#define fill(x,t) memset(x,t,sizeof(x))

typedef long long LL;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int N=1000005;

struct Matrix {
    LL arr[102][102];
} ;

LL f[N],sum[N],m;
int last[N],a[N];
int n,k;

LL read() {
    LL x=0,v=1; char ch=getchar();
    for (;ch<48||ch>57;v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<=57&&ch>=48;x=(x<<1)+(x<<3)+ch-48,ch=getchar());
    return x*v;
}

Matrix mul(Matrix a,Matrix b) {
    Matrix c;
    rep(i,1,k+1) rep(j,1,k+1) {
        c.arr[i][j]=0;
        rep(l,1,k+1) {
            c.arr[i][j]+=a.arr[i][l]*b.arr[l][j]%MOD;
        }
        c.arr[i][j]%=MOD;
    }
    return c;
}

Matrix ksm(Matrix x,LL dep) {
    Matrix ret=x; dep--;
    for (;dep;) {
        if (dep&1) ret=mul(ret,x);
        dep>>=1; x=mul(x,x);
    }
    return ret;
}

int main(void) {
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read(),m=read(),k=read(); sum[0]=1;
    rep(i,1,n) a[i]=read();
    rep(i,1,n) {
        if (!last[a[i]]) f[i]=sum[i-1];
        else f[i]=sum[i-1]-sum[last[a[i]]-1];
        f[i]+=(f[i]<0)?MOD:0; f[i]-=(f[i]>=MOD)?MOD:0;
        sum[i]=(sum[i-1]+f[i]); sum[i]-=(sum[i]>=MOD)?MOD:0;
        last[a[i]]=i;
    }
    last[0]=INF;
    rep(i,n+1,n+k) {
        int pos=0;
        rep(j,1,k) if (last[j]<last[pos]) {
            pos=j;
        }
        if (!last[pos]) f[i]=sum[i-1];
        else f[i]=(sum[i-1]-sum[last[pos]-1]);
        f[i]+=(f[i]<0)?MOD:0; f[i]-=(f[i]>=MOD)?MOD:0;
        sum[i]=sum[i-1]+f[i]; sum[i]-=(sum[i]>=MOD)?MOD:0;
        last[pos]=i;
    }
    if (k>=m) {
        printf("%lld\n", (sum[n+m]+MOD-1)%MOD);
        return 0;
    }
    Matrix wjp; fill(wjp.arr,0);
    rep(i,1,k) wjp.arr[i+1][i]=1;
    wjp.arr[k+1][k+1]=2; wjp.arr[1][k+1]=MOD-1;
    Matrix ret=ksm(wjp,m-k); LL ans=0;
    rep(i,1,k+1) ans=ans+sum[n+i-1]*ret.arr[i][k+1]%MOD;
    printf("%lld\n", (ans+MOD-1)%MOD);
    return 0;
}