Expected Waiting Time ZOJ - 3982

Expected Waiting Time ZOJ - 3982

选择的时候，选择屋子里的每一个人对对于答案的贡献都是相同的，所以可以直接看成选择最后一个，这样就变成了出栈和进栈的问题了
1 合法种类是卡特兰数，即n个人，那么合法数量就是h(n)
2 对于每一个位置，分析是出栈还是入栈
4 dp[i]代表第i个位置是出栈的可能情况,第i个位置出栈，那么假设第j个位置进栈，
5 我们有 $dp\left[i\right]=sum\left(dp\right[j\left]\right)j=i-1,i-3,i-\mathrm{5...}$dp[i]=sum(dp[j])j=i−1,i−3,i−5...那么中间的肯定是已经出栈进栈了，共有 h((i-j)/2)中可能
对于 1… j-1,i+1 …2n 这是一个出栈进栈的过程 所以h(n-(i-j)/2-1)
所以 $dp\left[i\right]=sum\left(h\right(i-j\left)/2\right)\ast h(n-(i-j)/2-1)=dp[i-2]+h\left(\right(i-1\left)/2\right)\ast h(n-(i-1)/2-1)$dp[i]=sum(h(i−j)/2)∗h(n−(i−j)/2−1)=dp[i−2]+h((i−1)/2)∗h(n−(i−1)/2−1)

const int maxn = 2e6+100;

LL a[maxn],b[maxn];
LL c[maxn];
LL inv[maxn];
LL dp[maxn]; // 用来存放种类数
LL n,p,A,B;

// 逆元打表和卡特兰数打表
void init(){
    inv[1] = 1;
    for(int i = 2;i <= n+1; ++i)
        inv[i] = (p - p/i*inv[p%i]%p)%p;
    c[0] = 1,c[1] = 1;
    for(int i = 2;i <= n; ++i)
        c[i] = (4*i-2)*inv[i+1]%p*c[i-1]%p;
}
int main(void)
{
    // init();
    int T;
    cin>>T;
    while(T--){
        
        scanf("%lld %lld %lld %lld %lld",&n,&p,&b[0],&A,&B);
        a[0] = 0;

        for(int i = 1;i <= 2*n; ++i)
            {
                b[i] = (A*b[i-1]+B)%p;
                a[i] = a[i-1]+b[i]+1;
                a[i] %= p;
            }
        init();
        dp[0] = dp[1] = 0;
        for(int i = 2;i <= 2*n; ++i){
            int j = (i>>1)-1;
            dp[i] = dp[i-2]+c[j]*c[n-j-1]%p;
            dp[i] %= p;

        }
        LL ans = 0;
        for(int i = 1;i <= 2*n; ++i){
            if(i != 1)
                ans += a[i]*dp[i]%p;
            ans %= p;
            if(i != 2*n)
                ans -= a[i]*dp[2*n-i+1]%p;
            ans %= p;
        }
        ans = ans*qpow(c[n],p-2,p)%p;
        printf("%lld\n",(ans%p+p)%p);

    }
    

   return 0;