首先我们令这 $k$ 对情侣坐在一起了，那么我们需要计算的就是这 $k$ 对情侣坐在一起的方案数乘上剩下的 $n-k$ 对情侣坐不到一起的方案数。
设 $f(i)$ 表示 $i$ 对情侣坐不到一起的的方案数，考虑如何转移，首先对于前 $i-1$ 对情侣，他们坐不到一起的方案数为 $f(i)$ ，现在来了一对情侣，那么现在就有 $i$ 个男的和 $i$ 个女的了。对于新的一排有三种情况：
- 对于新的一排，是两个男的。
- 对于新的一排，是两个女的。
- 对于新的一排，是一男一女 (非情侣)。
首先从现有的 $i$ 个男的中抽出两个男的的方案数为 $i\times(i-1)$ ，接着他们的配偶可以坐在一起也可以不坐在一起。先强制其不做在一起，那么我们可以将他们的配偶看作一对情侣 (同性恋？！)，然后方案数就是 $f(i-1)$ 了。坐在一起的话，那么也就是剩下 $i-2$ 对情侣来错排了，方案数显然为 $f(i-2)$ ，接着配偶们可以坐剩下 $i-1$ 排中的任意一排，并且坐下来后可以交换顺序，所以坐在一起的方案数为 $2(i-1)\times f(i-2)$ 。
为什么抽出两个男的坐一起不用交换呢，因为显然我们向上面那样计算后已经将交换的算进去了。
第二种情况显然和第一种情况相同。
第三种情况，先抽出一个男的方案数为 $i$ ，接着抽出一个女的 (注意不能抽出他的情侣) 的方案数为 $i-1$ ，然后对于抽出的男的的女朋友和抽出的女的的男朋友看做一对，这样子又和第一种情况没啥两样了。注意这种情况这两对男女是分别可以交换的。因为我们默认抽出一个男的放座位左边，抽出个女的放右边，但是抽出的这一排的这对男女在后面我们没有考虑女的坐座位左边的情况，所以当前新的一排的这对男女也要计算交换的贡献。
整理一下，可以得到转移式：
$$f(i)=(1+1+2)\times i(i-1)\times [f(i-1)+2(i-1)\times f(i-2)]$$
接着考虑 $k$ 对和睦的情侣的组成方案数，首先我们从 $n$ 对情侣中抽出 $k$ 对强制其和睦，那么这样子的方案数为 $C_{n}^{k}$ ，接着我们将这 $k$ 对情侣分配到 $n$ 排位置上，方案数为 $A_{n}^{k}$ ，然后这 $k$ 对情侣坐好后每一排情侣都可以交换座位，也就是说答案还得乘上 $2^k$ 就好了。
也就是说我们得到了 $k$ 对情侣坐在一起的方案数和剩下的 $n-k$ 对情侣坐不到一起的方案数，将其乘起来即可。
$$ans=2^k\times C_{n}^{k}\times A_{n}^{k}\times f(k)$$
这就是我们需要求的答案了，预处理一下后直接求，代码超级短~
时间复杂度 $O(nk)$ 。
Code：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+2;
#define p 998244353
int T,n;
ll f[N],A[N],M[N],fac[N],inv[N];
inline ll pow(ll x,ll y,ll res=1) {
for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
return res;
}
ll C(int m) {
return (fac[n]*inv[m]%p*inv[n-m]%p)%p;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
A[0]=M[0]=fac[0]=inv[0]=f[0]=1,f[1]=0;
for(int i=1;i<=n;++i) M[i]=2ll*M[i-1]%p;
for(int i=1;i<=n;++i) A[i]=1ll*A[i-1]*(n-i+1)%p;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p,inv[i]=pow(fac[i],p-2)%p;
for(int i=2;i<=n;++i) f[i]=4ll*i*(i-1)%p*(f[i-1]+2ll*(i-1)*f[i-2]%p)%p;
for(int k=0;k<=n;++k) {
ll ans=1ll*M[k]*C(k)%p*A[k]%p*f[n-k]%p;
printf("%lld\n",ans);
}
}
return 0;
}
以下为 $2019.6.6$ 更新：
至于加强版嘛…… 其实就是一个逗比，预处理阶乘和阶乘的逆元，组合和排列在询问的时候直接 $O(1)$ 算。然后因为 $f$ 数组也和 $n,k$ 没关系，放出来预处理，$M$ 数组自然可以预处理，也就是说我们将所有的数组提出来预处理，然后 $O(1)$ 回答即可。
时间复杂度 $O(n\log p+T)$ ，不需要卡，可以过的去，最慢的点 $860ms$ 。
Code：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=5e6+2;
#define p 998244353
int T,n,k;
ll dp[N],mul[N],fac[N],inv[N];
inline ll pow(ll x,ll y,ll res=1) {
for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
return res;
}
ll C(int n,int m) {return (fac[n]*inv[n-m]%p*inv[m]%p)%p;}
ll A(int n,int m) {return (fac[n]*inv[n-m]%p)%p;}
int main() {
mul[0]=fac[0]=inv[0]=dp[0]=1,dp[1]=0;
for(int i=1;i<=N-2;++i) mul[i]=2ll*mul[i-1]%p;
for(int i=1;i<=N-2;++i) fac[i]=1ll*fac[i-1]*i%p,inv[i]=pow(fac[i],p-2)%p;
for(int i=2;i<=N-2;++i) dp[i]=4ll*i*(i-1)%p*(dp[i-1]+2ll*(i-1)*dp[i-2]%p)%p;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&k);
ll ans=1ll*mul[k]*C(n,k)%p*A(n,k)%p*dp[n-k]%p;
printf("%lld\n",ans);
}
return 0;
}
0 条评论