JZOJ 6002 Permutation

THUWC 之前做的这题现在来补下题解。

x 有用吗……
显然如果确定了 Py，Px 的取值只有 ⌈Py2⌉−1 种。
故方案数为 n∑i=y(⌈i2⌉−1)(i−2)!(n−i)!(i−y)!。
很像卷积，随便推一下就成卷积了。
NTT 上。

题解里说 NTT 只有 80 分？
（看来这个出题人的 NTT 常数很大）

（实际上我不开 O2 2s+，开了 O2 700ms+）

代码：

#pragma GCC optimize (2)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;

const int BUFF_SIZE = 1 << 20;
namespace Read
{
    char BUFF[BUFF_SIZE],*BB,*BE;
    #define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
    template<class T>
    inline void read(T &x)
    {
        x = 0;
        char ch = 0,w = 0;
        for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
        for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
        w && (x = -x);
    }
};
namespace Write
{
    char BUFF[BUFF_SIZE],*BE = BUFF;
    inline void flush()
    {
        fwrite(BUFF,1,BE - BUFF,stdout);
    }
    inline void pc(char x)
    {
        if(BE - BUFF == BUFF_SIZE)
            flush(),BE = BUFF;
        *BE++ = x;
    }
    template<class T>
    inline void write(T x)
    {
        static int s[50],top;
        for(top = 0;x;s[++top] = x % 10,x /= 10);
        for(;top;pc(s[top--] + '0'));
        pc('\n');
    }
}
using Read::read;
using Write::write;

const int N = 1 << 21;
const int mod = 998244353;
const int G = 3;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
struct poly
{
    int a[N + 5];
    inline const int &operator[](int x) const
    {
        return a[x];
    }
    inline int &operator[](int x)
    {
        return a[x];
    }
    inline void clear(int x = 0)
    {
        memset(a + x,0,(N - x + 1) << 2);
    }
} f,g,ans;
int len,q,n,lg2[N + 5];
int rev[N + 5],fac[N + 5],ifac[N + 5],inv[N + 5];
int rt[N + 5],irt[N + 5];
inline void init(int len)
{
    for(n = 1;n < len;n <<= 1);
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i >> 1] + 1;
    int w = fpow(G,(mod - 1) / n);
    rt[n >> 1] = 1;
    for(register int i = (n >> 1) + 1;i <= n;++i)
        rt[i] = (long long)rt[i - 1] * w % mod;
    for(register int i = (n >> 1) - 1;i;--i)
        rt[i] = rt[i << 1];
    fac[0] = 1;
    for(register int i = 1;i <= n;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[n] = fpow(fac[n],mod - 2);
    for(register int i = n;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    for(register int i = 1;i <= n;++i)
        inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
}
inline void ntt(poly &a,int type,int n)
{
    type == -1 && (reverse(a.a + 1,a.a + n),1);
    int lg = lg2[n] - 1;
    for(register int i = 0;i < n;++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
        i < rev[i] && (swap(a[i],a[rev[i]]),1);
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
            {
                int t = (long long)rt[m | j] * a[i | j | m] % mod;
                a[i | j | m] = dec(a[i | j],t),a[i | j] = add(a[i | j],t);
            }
    if(type == -1)
        for(register int i = 0;i < n;++i)
            a[i] = (long long)a[i] * inv[n] % mod;
}
inline void mul(poly &a,const poly &b,int n)
{
    static poly x,y;
    int lim = 1;
    for(;lim < (n << 1);lim <<= 1);
    memcpy(x.a,a.a,lim << 2),memcpy(y.a,b.a,lim << 2);
    memset(x.a + n,0,lim - n + 1 << 2),memset(y.a + n,0,lim - n + 1 << 2);
    ntt(x,1,lim),ntt(y,1,lim);
    for(register int i = 0;i < lim;++i)
        x[i] = (long long)x[i] * y[i] % mod;
    ntt(x,-1,lim);
    memcpy(a.a,x.a,lim << 2);
}
int main()
{
    freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout);
    read(len),read(q),init((len + 1) << 1);
    for(register int i = 0;i <= len;++i)
        f[i] = len - i >= 2 ? (long long)((len - i + 1) / 2 - 1) * fac[len - i - 2] % mod : 0,
        g[i] = ifac[i];
    mul(f,g,len + 1);
    for(register int i = 0;i <= len;++i)
        ans[i] = (long long)fac[len - i] * f[len - i] % mod;
    for(int x,y;q;--q)
        read(x),read(y),write(ans[y]);
    Write::flush();
}