Problem

題目鏈接

Solution

吼題啊吼題！

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

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

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

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

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

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

轉(zhuǎn)載于:https://www.cnblogs.com/YoungNeal/p/9780949.html

總結(jié)

以上是生活随笔為你收集整理的[JZOJ5836] Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。