[JZOJ5836] Sequence

摘要： Problem 題目連結 Solution 吼題啊吼題！ 首先如何求本質不同的子序列個數就是\(f[val[i]]=1+\sum\limits_{j=1}^k f[j]\) 其中\(f[i]\) 表示的是以\(i\) 結尾的...

Problem

ofollow,noindex" target="_blank">題目連結

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;
}