题目大意:
给定一个序列以及一个字符集合,要求在后面添加m个集合中的字符使得总的字符串中的本质不同子序列数量尽可能多。
思路:
考虑怎么DP来计算本质不同子序列个数,设
dp[i]
d
p
[
i
]
为以
i
i
结尾的本质不同子序列个数,它的个数等于之前的所有的本质不同子序列个数之和+1。因为可以看成之前所有的本质不同子序列都在后面加上了一个,最后再算上单独一个
i
i
。所以,发现单次转移不论对于哪一个字符值都是固定的,所以为了让最后的和最大,所以选择目前dp值最小的那个转移。
这样以后发现每
k
k
次转移的字符都是完全相同的一个轮回,所以只需要矩阵快速幂优化DP就好了。这里有一个小技巧就是并不要把次转移的矩阵乘起来当作一次转移,我们可以先按照转移的顺序排序dp数组,然后单次转移的时候先转移第一个并且把它放到最后面,然后把后面的所有的数都往前面平移一个。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
using namespace std;
void File(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
}
const int maxn=1e6+10;
const int maxk=100+10;
const ll mod=1e9+7;
int n,k,s[maxn];
ll m;
pair<ll,int>dp[maxn];
struct Matrix{
ll a[maxk][maxk];
Matrix operator * (const Matrix & b) const {
Matrix c;
REP(i,1,k+1)REP(j,1,k+1){
ll sum=0;
REP(p,1,k+1)sum=(sum+a[i][p]*b.a[p][j])%mod;
c.a[i][j]=sum;
}
return c;
}
}Ma;
bool cmp(pair<ll,int> a,pair<ll,int> b){
return a.second<b.second;
}
void work(){
ll sum=0;
REP(i,1,n){
dp[s[i]].second=i;
ll tmp=dp[s[i]].first;
dp[s[i]].first=sum+1;
sum=(sum-tmp+dp[s[i]].first)%mod;
}
sort(dp+1,dp+k+1,cmp);
dp[k+1].first=1;
REP(j,1,k-1)Ma.a[j+1][j]=1;
REP(i,1,k+1)Ma.a[i][k]=1;
Ma.a[k+1][k+1]=1;
Matrix ans;
REP(i,1,k+1)ans.a[i][i]=1;
while(m){
if(m&1)ans=ans*Ma;
Ma=Ma*Ma;
m>>=1;
}
ll Ans=0;
REP(j,1,k+1)REP(p,1,k+1)
Ans=(Ans+dp[p].first*ans.a[p][j])%mod;
printf("%lld\n",(Ans-1+mod)%mod);
}
int main(){
File();
scanf("%d%lld%d",&n,&m,&k);
REP(i,1,n)scanf("%d",&s[i]);
work();
return 0;
}
更多推荐
[CF655E]Intellectual Inquiry——DP+矩阵快速幂优化
发布评论