codeforces 666C Codeword

题意

q个询问，一种询问是给你一个字符串，还有一种是问长度为n的，包含当前字符串为子序列的字符串有多少个。

题解

容易写出式子，但是不好化简。

观察一下可以知道q个询问的字符串长度也就根号种。

代码

#include
    
     using namespace std;#define fi first#define se second#define mp make_pair#define pb push_back#define rep(i, a, b) for(int i=(a); i<(b); i++)#define sz(a) (int)a.size()#define de(a) cout << #a << " = " << a << endl#define dd(a) cout << #a << " = " << a << " "#define all(a) a.begin(), a.end()#define endl "\n"typedef long long ll;typedef pair
     
       pii;typedef vector
      
        vi;//---const int N = 101010, P = 1e9+7;int pw[N], jc[N], in[N], ans[N];vector
       
         Q[N];inline int mul(int a, int b) {    return a * 1ll * b % P;}inline int add(int a, int b) {    int res = a+b;    if(res >= P) res -= P;    return res;}inline int kpow(int a, int b) {    int res = 1;    while(b) {        if(b&1) res = mul(res, a);        a = mul(a, a);        b >>= 1;    }    return res;}inline void init() {    pw[0] = 1;    rep(i, 1, N) pw[i] = mul(pw[i-1], 25);    jc[0] = 1;    rep(i, 1, N) jc[i] = mul(jc[i-1], i);    in[N-1] = kpow(jc[N-1], P-2);    for(int i = N-2; ~i; --i) in[i] = mul(in[i+1], i+1);}inline int C(int n, int m) {    if(n < m) return 0;    return mul(jc[n], mul(in[m], in[n-m]));}int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(0);    init();    int n, m, q;    string s;    cin >> q >> s;    m = sz(s);    rep(i, 0, q) {        int x;        cin >> x;        if(x == 1) {            cin >> s;            m = sz(s);        } else {            cin >> n;            Q[m].pb(mp(n, i));        }    }    rep(m, 0, N) if(sz(Q[m])) {        sort(all(Q[m]));        int i = m, res = 1;        for(auto t : Q[m]) {            int n = t.fi;            while(i < n) {                ++i;                res = mul(res, 26);                res = add(res, mul(C(i-1, m-1), pw[i - m]));            }            ans[t.se] = n >= m ? res : 0;            ++ans[t.se];        }    }    rep(i, 0, q) if(ans[i]) {        cout << ans[i]-1 << endl;    }    return 0;}