T1 数数

回来补一下\(n\)天前的考试题.

很明显,我们通过枚举\(l\)与\(r\),可以得到一个式子：

\(Ans = \sum_{i = r}^{n}(n - r)! * \sum_{j = 1}^{\lfloor { \frac{(i - 1)}{2}}\rfloor}P^{r -2}_{i - 2}\)

发现这个式子的值和\(l\)没任何关系,然后我们想办法化简一下

\(Ans = (n - r)!\sum_{i = r}^n*\lfloor\frac{(i - 1)}{2}\rfloor *\frac{(i - 2)!}{(i - r)!}\)

因为模数是\(998244353\),我们尽量向卷积上靠

设：

\(f(i) = \lfloor\frac{(i - 1)}{2}\rfloor * (i - 2)!\)

\(g(i) = \frac{1}{i!}\)

那么则有

\(Ans = (n - r)!\sum_{i = r}^nf(i)g(i - r)\)

发现貌似不能直接上卷积,我们只会套\(f(i)g(r - i)\)这样的

那我们就设

\(g'(i) = g(n - i)\)

那么有

\(Ans = (n - r)!\sum_{i = r}^nf(i)g'(n + r - i)\)

这样我们直接将\(g'\)与\(f\)卷积,新的多项式的第\(n + i\)项就是\(r = i\)时的答案

时间复杂度\(O(nlog(n))\)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int N = 1e5 + 3;
const LL mod = 998244353;
LL a[N << 3],b[N << 3],g[N << 3];
int r[N << 3];
LL fac[N << 3],ans[N << 3];
int n,m,limit = 1,l,q;
inline LL quick(LL a,LL b){
    LL res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
inline void nttle(LL *A,int type){
    for(int i = 0;i < limit;++i)
        if(i < r[i]) swap(A[i],A[r[i]]);
    for(int mid = 1;mid < limit;mid <<= 1){
        LL Wn = (type == 1) ? quick(3,(mod - 1) / (mid << 1)) :
        quick(3,mod - 1 - (mod - 1) / (mid << 1));
        for(int R = mid << 1,j = 0;j < limit;j += R){
            LL w = 1;
            for(int k = 0;k < mid;++k,w = w * Wn % mod){
                LL x = A[j + k],y = A[j + k + mid] * w % mod;
                A[j + k] = x + y;
                A[j + k + mid] = x - y;
                if(A[j + k] >= mod) A[j + k] -= mod;
                if(A[j + k + mid] < 0) A[j + k + mid] += mod;
            }
        }
    }
    if(type == -1){
        LL inv = quick(limit,mod - 2);
        for(int i = 0;i < limit;++i) A[i] = A[i] * inv % mod;
    }
}
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar(); 
    }   
    return v * c;
}   
int main(){
    n = read();q = read();
    fac[0] = 1;
    for(int i = 1;i <= n;++i) fac[i] = fac[i - 1] * i % mod;
    for(int i = 0;i <= n;++i){
        a[i] = (i >= 2) ? ((i - 1) / 2) * fac[i - 2] % mod : 0;
        b[i] = quick(fac[i],mod - 2);   
    } 
    reverse(b,b + n + 1);
    //for(int i = 1;i <= n;++i) g[i] = b[n - i + 1];

//  for(int i = 1;i <= n;++i) printf("%lld ",b[i]);puts("");
    while(limit < 2 * (n + 1)) limit <<= 1,++l;
//  cout << limit << endl; 
    for(int i = 0;i < limit;++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); 
    //for(int i = 0;i < limit;++i) printf("%d ",r[i]);puts("");
    nttle(a,1);
    nttle(b,1);//for(int i = 0;i < limit;++i) printf("%lld ",b[i]);puts("");
    for(int i = 0;i < limit;++i) a[i] = a[i] * b[i] % mod;
    nttle(a,-1);    
    for(int i = 2;i <= n;++i) ans[i] = fac[n - i] * a[n + i] % mod;
    while(q--){
        int x = read(),y = read();
        printf("%lld\n",ans[y]);
    }
    return 0;   
}

ZR冬令营集训D4

原文：https://www.cnblogs.com/wyxdrqc/p/10627891.html