[MtOI2018]情侣？给我烧了！
为什么总是不能一遍过呢？
复读的，但觉得这个方法有点七拐八绕的。。。可能是所谓的推组合式子会比较繁琐？
设 $f_k$ 表示恰好 $k$ 对坐在一起的方案数，$d_k$ 表示 $k$ 对座两列，没有一对相邻的个数，则：
$$f_k=\binom{n}{k}^2k!2^kd_{n-k}$$
表示的意思是先从 $n$ 对中挑出 $k$ 对，再从 $n$ 排中挑出 $k$ 排，情侣内部的左右顺序，最后剩下的人全部不能坐在一起。
现在用二项式反演求 ${d}$。
设 $g_{n,k}$ 表示 $n$ 对中选 $k$ 对坐在一起，剩余的人随意的方案数，则：
$$\begin{aligned}
g_{n,k}
&=\binom{n}{k}^2k!2^k(2(n-k))!
\\
&=\sum_{i=k}^{n}\binom{i}{k}f_{n,i}
\end{aligned}$$
则：
$$f_{n,k}=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}g_{n,i}$$
则：
$$\begin{aligned}d_n&=f_{n,0}=\sum_{i=0}^{n}(-1)^ig_{n,i}
\\
&=\sum_{i=0}(-1)^i\binom{n}{i}^2i!2^i(2(n-i))!
\end{aligned}$$
然后就是 $O(n^2)$ 预处理，$O(Tn)$ 求解了。。。
代码：
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}
using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll N=2e3,mo=998244353;
ll T,n;
ll c[N+5][N+5],fac[N+5],pw2[N+5],d[N+5];
inline void Init() {
c[0][0]=1;
for(ll i=1;i<=N;i++) {
c[i][0]=1;
for(ll j=1;j<=i;j++) {
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
}
}
fac[0]=1;for(ll i=1;i<=N;i++) {fac[i]=fac[i-1]*i%mo;}
pw2[0]=1;for(ll i=1;i<=N;i++) {pw2[i]=pw2[i-1]*2ll%mo;}
for(ll i=0;i*2<=N;i++) {
for(ll j=0;j<=i;j++) {
ll tmp=1;
tmp=tmp*c[i][j]%mo;
tmp=tmp*c[i][j]%mo;
tmp=tmp*fac[j]%mo;
tmp=tmp*pw2[j]%mo;
tmp=tmp*fac[2*(i-j)]%mo;
if(j&1) d[i]=(d[i]-tmp+mo)%mo;
else d[i]=(d[i]+tmp)%mo;
}
}
}
int main() {
T=read();Init();
while(T--) {
n=read();
for(ll i=0;i<=n;i++) {
ll tmp=1;
tmp=tmp*c[n][i]%mo;
tmp=tmp*c[n][i]%mo;
tmp=tmp*fac[i]%mo;
tmp=tmp*pw2[i]%mo;
tmp=tmp*d[n-i]%mo;
writeln(tmp);
}
}
return 0;
}
|