[CodeForces-759D]Bacterial Melee

题目大意：
　　有一串n个字母，每个位置的字母可以同化边上的一个字母，
　　比如：ab可以变成aa或者bb。
　　相对的两个同化不能同时发生，比如ab不能变成ba。
　　现在给你一个字符串，问你经过任意次数的同化过程，最多能生成多少个字符串。

思路：
　　考虑同化过后的字符串与同化前的字符串的关系。
　　如果我们把一个字符串中相邻且相同的字母缩在一起，那么我们可以发现每一次同化就相当于从原串中去掉了一个字符。
　　这也就意味着同化过后的串一定是原串的一个子序列。
　　同样，如果一个串是原串的一个子序列，它一定能由原串同化而来。
　　我们可以先统计一下原串不同长度子序列的个数。
　　对于一个长度为l的子序列，它里面有n-l个字符被缩过，那么缩之前的串总共有C(n,l)种可能。
　　不同的子序列数量可以用DP求出来。
　　f[i][j]表示以字符j结尾的长度为i的子序列数量，则f[i][j]=sum{f[i-1][k]|k≠j}+1，枚举i,j,k，时间复杂度O(n^2*26)。
　　如果直接枚举k会TLE，只能过11个点，我们可以考虑用sum[i]记录长度为i的子串的数量和。
　　由于结尾位置的字符已确定，所以组合数用C(n-1,l-1)算，时间复杂度O(n^2)。

 #include<cstdio>

 #include<cctype>

 typedef long long int64;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,SIGMA=,mod=1e9+;

 char s[N];

 int f[N][SIGMA],sum[N],fact[N],factinv[N];

 inline int idx(const char &ch) {

     return ch-'a'+;

 }

 void exgcd(const int &a,const int &b,int &x,int &y) {

     if(!b) {

         x=;

         y=;

         return;

     }

     exgcd(b,a%b,y,x);

     y-=a/b*x;

 }

 inline int inv(const int &x) {

     int ret,tmp;

     exgcd(x,mod,ret,tmp);

     return (ret%mod+mod)%mod;

 }

 inline int C(const int &n,const int &m) {

     return (int64)fact[n]*factinv[n-m]%mod*factinv[m]%mod;

 }

 int main() {

     const int n=getint();

     scanf("%s",s);

     fact[]=factinv[]=;

     for(register int i=;i<n;i++) {

         fact[i]=(int64)fact[i-]*i%mod;

         factinv[i]=inv(fact[i]);

     }

     sum[]=;

     for(register int i=;i<n;i++) {

         const int ch=idx(s[i]);

         for(register int i=;i<=n;i++) {

             sum[i]=(sum[i]-f[i][ch]+mod)%mod;

             f[i][ch]=(sum[i-]-f[i-][ch]+mod)%mod;

             sum[i]=(sum[i]+f[i][ch])%mod;

         }

     }

     int ans=;

     for(register int i=;i<=n;i++) {

         ans=(ans+(int64)C(n-,i-)*sum[i]%mod)%mod;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

[CodeForces-759D]Bacterial Melee

最新文章

热门文章