A 了这道题+发这篇题解,就当过了这个七夕节吧
奇怪的过节方式又增加了
首先看到此题第一眼我们可以想到二项式反演,不过这个 \(T\) 组数据加上 \(5\times 10^6\) 的数据范围肯定是反演不动的,因此考虑怎样不反演。
我们很显然可以将求解这个问题划分成两部分:选出 \(k\) 对相邻的情侣并将它们的位置安排好+排列好剩下 \(n-k\) 对情侣。两部分显然是独立的,因此分别考虑。第一部分是是比较容易的,选出 \(k\) 对情侣方案数 \(\dbinom{n}{k}\),选出 \(k\) 排位置方案数 \(\dbinom{n}{k}\),将这 \(k\) 对与 \(k\) 排座位对应方案数 \(k!\),将 \(k\) 对情侣随意调换位置 \(2^k\),因此第一部分方案数就是 \(\dbinom{n}{k}^2k!2^k\)。第二部分显然可以等效于求安排好 \(n-k\) 对情侣的方案数,假设这东西为 \(f_{n-k}\),显然这东西是要预处理的,考虑怎么预处理 \(f_n\)。注意到这东西跟错排数长得很像但又不完全一致,因此考虑错排数的套路,我们枚举第一排是哪两个人坐在一起的,那么方案数为 \(2n·(2n-2)\),第二个地方要减 \(2\) 因为一个人不能和自己的情侣坐在一起,那么考虑这两个人的 boy/girlfriend 是否坐在一起,如果它们坐在一起那不错,这两对 couple 就消失了,剩余部分就是 \(f_{n-2}\),不过安排好第一排这两个人的 boy/girlfriend 还需乘上个 \(2(n-1)\),因为要选择一排给他们坐,他们的位置还可以交换,因此需乘个 \(2\)。如果它们不坐一起,那么我们就把这东西当作一个限制条件,强制令它们贴贴,形成一对新的 couple,这样问题就规约为 \(f_{n-1}\),因此我们得到了递推式 \(f_n=2n·(2n-2)(f_{n-1}+2(n-1)f_{n-2})\),线性求一下即可。
时间复杂度 \(\mathcal O(n+T)\)
祝大家七夕节快乐
const int MAXN=5e6;
const int MOD=998244353;
int fac[MAXN+5],ifac[MAXN+5],pw2[MAXN+5],f[MAXN+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=pw2[0]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) ifac[i]=1ll*ifac[i]*ifac[i-1]%MOD,fac[i]=1ll*fac[i-1]*i%MOD,pw2[i]=(pw2[i-1]<<1)%MOD;
f[0]=1;for(int i=2;i<=n;i++) f[i]=4ll*i*(i-1)%MOD*(f[i-1]+2ll*(i-1)*f[i-2]%MOD)%MOD;
}
int binom(int x,int y){
if(x<0||y<0||x<y) return 0;
return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int main(){
init_fac(MAXN);int qu;scanf("%d",&qu);
while(qu--){
int n,k;scanf("%d%d",&n,&k);
printf("%d\n",1ll*binom(n,k)*binom(n,k)%MOD*pw2[k]%MOD*fac[k]%MOD*f[n-k]%MOD);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章