[JZOJ5836] Sequence

Problem

題目鏈接

Solution

吼題啊吼題！

首先如何求本質不同的子序列個數就是 \(f[val[i]]=1+\sum\limits_{j=1}^k f[j]\)

其中 \(f[i]\) 表示的是以 \(i\) 結尾的子序列個數

先把原數列的不同子序列個數求出來，然后觀察一下這個轉移，貪心的發現每次都是選一個最早出現的 \(i\) 填到序列末尾，然后更新這個值。

所以填的部分一定是 \(\frac mk\) 個 \(K\) 的排列，還有多出來了 \(m\%k\) 個元素暴力填進去。

每 \(K\) 個元素的轉移是一樣的，可以拿矩乘做。然后多余的部分求前綴積暴力求就行了。

Code

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
using std::vector;
const int N=105;
const int M=1e6+5;
typedef double db;
typedef long long ll;
#define int long long
const int mod=1e9+7;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define mp(A,B) std::make_pair(A,B)int n,m,k,per[M];
int val[M];pii las[M];struct Mat{int a[N][N];void clear(){memset(a,0,sizeof a);}void init(){clear();for(int i=1;i<=k+1;i++)a[i][i]=1;}void print(){for(int i=1;i<=k+1;i++,puts(""))for(int j=1;j<=k+1;j++)printf("%lld ",a[i][j]);}friend Mat operator*(Mat x,Mat y){Mat z;z.clear();for(int i=1;i<=k+1;i++){for(int p=1;p<=k+1;p++){for(int j=1;j<=k+1;j++)z.a[i][j]=(z.a[i][j]+x.a[i][p]*y.a[p][j]%mod)%mod;}} return z;}
}cs,f,qzh[N];int getint(){int X=0,w=0;char ch=0;while(!isdigit(ch))w|=ch=='-',ch=getchar();while( isdigit(ch))X=X*10+ch-48,ch=getchar();if(w) return -X;return X;
}Mat ksm(Mat x,int y){Mat ans;ans.init();while(y){if(y&1) ans=ans*x;x=x*x;y>>=1;} return ans;
}signed main(){freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);n=getint(),m=getint(),k=getint();int sum=0;f.clear();f.a[1][k+1]=1;for(int i=1;i<=k;i++) las[i]=mp(0,i);for(int i=1;i<=n;i++){val[i]=getint();int p=f.a[1][val[i]];f.a[1][val[i]]=(sum+1)%mod;sum-=p;sum+=f.a[1][val[i]];sum%=mod;las[val[i]]=mp(i,val[i]);} std::sort(las+1,las+1+k);qzh[0].init();for(int i=1;i<=k;i++){per[i]=las[i].second;qzh[i].clear();for(int j=1;j<=k+1;j++) qzh[i].a[j][j]=1;for(int j=1;j<=k+1;j++) qzh[i].a[j][per[i]]=1;qzh[i]=qzh[i-1]*qzh[i];} cs=ksm(qzh[k],m/k);cs=cs*qzh[m%k];f=f*cs;int ans=0;for(int i=1;i<=k;i++) (ans+=f.a[1][i])%=mod;printf("%lld\n",ans);return 0;
}