题解 | #串#

A题题解

思路

使用动态规划。
我们不妨令 L[i] 来表示长度为i的且含序列"us"的字符串的种类
对于L[i]进行集合划分：
① 在第i个字符前“us”已经产生，所以第i个字符可以任意取 => L[i-1]*26
② 在第i个字符时才产生“us”，此时第i个字符一定是‘s’   =>  x[i-1]:长度为i-1的且含‘u’但不含“us”的字符串的种类

 => L[i] = L[i-1]*26 + x[i-1]

所以这就要求我们记录 一个 x 数组
不妨令x[i]：长度为i的且含'u'但不含“us”的字符串的种类
集合划分：
① 在第i个字符前出现过了'u'，所以第i个字符取's'以外的字符  => x[i-1]*25
② 在第i个字符时才出现字符‘u’,所以此前一定不含'u'且第i个字符一定为‘u’  => y :长度为i-1的且不含字符‘u’的字符串的种类

 => x[i] = x[i-1]*25 + y

 y = 25^(i-1) 

又因为需要取模，所以我们可以得到如下的式子：
(1) L[i] = (L[i-1]*26 + x[i-1])%MOD 
(2) x[i] = (x[i-1]*25 + 25^(i-1))%MOD


综上 Code如下：

code

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e6+10;
const int MOD=1e9+7;

typedef long long ll;

ll x[N];
ll L[N];
ll ans;
int n;

/*
x[i]：长度为i的且含‘u’但不含“us”的字符串的种类
L[i]：长度为i的且含"us"的字符串的种类
*/

ll qpow(ll a,ll b){
    ll base=a%MOD;
    ll res=1;

    while(b){
      if(b&1) res=(res*base)%MOD;
      base=(base*base)%MOD; 
      b>>=1;   
    }

    return res;   
}

int main(){
    cin>>n;

    x[1]=1; // x数组初始化
    for(int i=2;i<=n;i++){
       L[i] = (L[i-1]*26 + x[i-1]) % MOD ;
       x[i] = (x[i-1]*25 + qpow(25,i-1)) % MOD ;
       ans = (ans + L[i]) % MOD;
    }        

    cout<<ans<<endl;    

    return 0;
}