Luogu4548 CTSC2006 歌唱王国 概率生成函数、哈希

传送门

---

orz ymd

考虑构造生成函数：设(F(x) = sumlimits_{i=0}^infty f_ix^i)，其中(f_i)表示答案为(i)的概率；又设(G(x) = sumlimits_{i=0}^infty g_ix^i)，其中(g_i)表示经过了(i)步之后还没有结束的概率。那么答案显然是(F'(1))。

考虑在还没有结束的序列之后加入一个字符，那么有可能结束也有可能没有结束，即(F(x) + G(x) = xG(x) + 1)。

两边求导并将(x=1)代入可以得到(F'(1) = G(1))。

接下来考虑在还没有结束的序列之后加入当前需要匹配的字符串，那么一定会结束，但有可能已经存在一个前缀满足条件。设(a_i)表示原字符串是否有长度为(i)的border，那么不难得到(G(x)(frac{x}{n})^m = sumlimits_{i=1}^m a_iF(i)(frac{x}{n})^{m-i})。

将(x=1)代入可以得到(G(1) = sumlimits_{i=1}^m a_in^i)

那么使用哈希或者KMP求出所有的(a_i)即可求出答案。

#include<bits/stdc++.h>
//this code is written by Itst
using namespace std;

int read(){
    int a = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)){
        a = a * 10 + c - 48; c = getchar();
    }
    return a;
}

#define int long long
const int _ = 1e5 + 7;
const int seed = 2344259 , MOD = 134093753;
int powsd[_] , N , T , M;

namespace Hashing{
    int val[_];

    void init(int len){
        for(int i = 1 ; i <= len ; ++i)
            val[i] = (1ll * val[i - 1] * seed + read()) % MOD;
    }

    int qry(int l , int r){return (val[r] - val[l - 1] * powsd[r - l + 1] % MOD + MOD) % MOD;}
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    powsd[0] = 1; powsd[1] = seed;
    for(int i = 2 ; i <= 1e5 ; ++i)
        powsd[i] = 1ll * powsd[i - 1] * seed % MOD;
    N = read() % 10000; T = read();
    for(int i = 1 ; i <= T ; ++i){
        int L = read() , sum = 0 , tms = N; Hashing::init(L);
        for(int j = 1 ; j <= L ; ++j , tms = tms * N % 10000)
            if(Hashing::qry(1 , j) == Hashing::qry(L - j + 1 , L))
                sum = (sum + tms) % 10000;
        printf("%04lld
" , sum);
    }
    return 0;
}