THUWC 之前做的这题现在来补下题解。
\(x\) 有用吗……
显然如果确定了 \(P_y\)，\(P_x\) 的取值只有 \(\lceil \frac{P_y}2 \rceil - 1\) 种。
故方案数为 \(\sum\limits_{i=y}^n (\lceil \frac i2 \rceil - 1) (i-2)! \frac{(n-i)!}{(i-y)!}\)。
很像卷积，随便推一下就成卷积了。
NTT 上。
题解里说 NTT 只有 80 分？
（看来这个出题人的 NTT 常数很大）
（实际上我不开 O2 2s+，开了 O2 700ms+）
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
using namespace std;
const int BUFF_SIZE = 1 << 20;
namespace Read
{
char BUFF[BUFF_SIZE],*BB,*BE;
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();
}