#错排，排列组合#洛谷 4921 洛谷 4931 情侣？给我烧了

题目

分析

这里讲的是加强版，希望 O ( 1 ) O(1) O(1)回答

在 n n n排选择 m m m排座位的方案是 C ( n , m ) C(n,m) C(n,m)，在 n n n对情侣中选择 m m m对和睦的情侣坐在这 m m m排位置上，方案是 P ( n , m ) P(n,m) P(n,m)，每排的座位都可以交换坐，所以方案为 2 m 2^m 2m，剩下的不和睦的方案把它设为 d p [ n − m ] dp[n-m] dp[n−m]

那么答案就是 C ( n , m ) ∗ P ( n , m ) ∗ 2 m ∗ d p [ n − m ] C(n,m)*P(n,m)*2^m*dp[n-m] C(n,m)∗P(n,m)∗2m∗dp[n−m]

关键是 d p [ k ] dp[k] dp[k],对于一对情侣，若一个在左上角，有 2 k 2k 2k种选择，而右上角有 2 k − 2 2k-2 2k−2种选择，分类讨论

• 若右上角的配偶跟左上角的配偶在同一排，那么他们一个坐在一边，另一个坐在另一边，剩下的就是 k − 2 k-2 k−2对不和谐的情侣，所以是 ( 2 k − 2 ) d p [ k − 2 ] (2k-2)dp[k-2] (2k−2)dp[k−2]
• 若不在同一排，那么可以认为他们是同一对不和谐的情侣，所以是 d p [ k − 1 ] dp[k-1] dp[k−1]

综上所述, d p [ k ] = 4 k ( k − 1 ) ( 2 ( k − 1 ) d p [ k − 2 ] + d p [ k − 1 ] ) dp[k]=4k(k-1)(2(k-1)dp[k-2]+dp[k-1]) dp[k]=4k(k−1)(2(k−1)dp[k−2]+dp[k−1])

以上的东西预处理 O ( 1 ) O(1) O(1)回答

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=5000001,mod=998244353;
int fac[N],inv[N],dp[N],mi[N];
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
signed main(){
    fac[0]=fac[1]=inv[0]=inv[1]=dp[0]=mi[0]=1; mi[1]=2;
    for (rr int i=2;i<N;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod,mi[i]=2ll*mi[i-1]%mod;
    for (rr int i=2;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for (rr int i=2;i<N;++i) dp[i]=(1ll*(1ll*dp[i-2]*(2*i-2)+dp[i-1])%mod*i%mod*(i-1)<<2)%mod;
    for (rr int t=iut();t;--t){
        rr int n=iut(),k=iut();
        print(1ll*fac[n]*fac[n]%mod*inv[k]%mod*inv[n-k]%mod*inv[n-k]%mod*mi[k]%mod*dp[n-k]%mod);
        putchar(10);
    }
    return 0;
}