【数学】[MtOI2018]情侣？给我烧了！
不会生成函数 /yun
弱化版直接二项式反演乱搞做差卷积就好了。
考虑 \(f[i]\) 为至少 \(i\) 对情侣坐一起的方案数，显然 \(f[i]=\binom{n}{i}\binom{n}{i}i!2^i*(2n-2i)!\)，即钦定 \(i\) 对情侣，\(i\) 排座位，情侣座位选择可以全排列，每对情侣可以选择是否交换座位，剩下的随便坐。
\(g[i]\) 为恰好 \(i\) 对情侣坐一起。
\[f[i]=\sum_{j=i}^n\binom{j}{i}g[j] \]\[g[j]=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}f[j] \]套路化一下发现可以 NTT 优化。
强化版考虑正难则反，能不能搞出 \(i\) 对情侣错排情况数？能的话就好做了。只要钦定 \(k\) 对情侣坐一起，剩下的错排开就好了。
设 \(g[i]\) 为只有 \(i\) 对情侣且每对情侣都错排开的情况数。\(g[0]=1,g[1]=0\)。
\[g[i]=2i(2i-2)(g[i-1]+2(i-1)g[i-2]) \]因为是递推，所以可以不考虑各排的排列，因为每次新加入的人的不同已经等价于了。
或者说，你可以认为每次进来的人都去第一排，那么每次进来的人可能不一样，所以各排间的全排列不需要。
随便选 2 个不是情侣的人，然后要不要选他们的情侣，那我们当前问题的规模就减小 1。假如选他们的情侣，那么规模减小 2，再选他们的情侣所在的排。
事实上这种组合意义这么 nb 的我在考场上也应该想不到，倒是弱化版挺一眼的。
#include
#define int long long
#define pb push_back
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
#define N 2005
#define M (int)(4e5+5)
const int mod=998244353,G=3;
int fpow(int x,int y) {
int res=1;
while(y) {
if(y&1) res=res*x%mod;
y>>=1; x=x*x%mod;
}
return res;
}
const int invG=fpow(G,mod-2);
void NTT(int *f,int n,bool fl=1) {
static int tr[M];
for(int i=0;i>1]>>1)|((i&1)?(n>>1):0);
for(int i=0;i>1),w=fpow(fl?G:invG,(mod-1)/p);
for(int l=0;ln||n<0||m<0) return 0;
return jie[n]*djie[m]%mod*djie[n-m]%mod;
}
void solve() {
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
n=rd(); f[0]=jie[2*n];
for(int i=1;i<=n;i++) f[i]=C(n,i)*C(n,i)%mod*jie[i]%mod*fpow(2,i)%mod*jie[2*n-2*i]%mod;
// 太屑了 不放 n^3 ，你玩nmd，是个紫就要 NTT 做差卷积？？
// 老子今天都不知道写几遍 NTT 了
for(int i=0;i<=n;i++) f[i]=jie[i]*f[i]%mod;
for(int i=0;i<=n;i++) g[i]=((i&1)?-1:1)*djie[i]%mod;
reverse(f,f+1+n);
int m; for(m=1;m #include
#define int long long
#define pb push_back
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
#define N (int)(5e6+5)
const int mod=998244353;
int g[N],jie[N],djie[N];
int fpow(int x,int y) {
int res=1; x%=mod;
while(y) {
if(y&1) res=res*x%mod;
y>>=1; x=x*x%mod;
}
return res;
}
int C(int n,int m) {
return jie[n]*djie[m]%mod*djie[n-m]%mod;
}
void solve() {
int n,k,ans=0;
cin>>n>>k;
ans=C(n,k)*C(n,k)%mod*jie[k]%mod*fpow(2,k)%mod*g[n-k]%mod;
ans=(ans%mod+mod)%mod;
cout<>T; while(T--) solve();
return 0;
}