题解 | 小红的好排列

这是一道数学组合题，类似于高中排列组合那一章的一道题吧，只需要推出来式子

我们知道我们需要ned=n/2个

我们已经有cnt=n/3个满足条件

还需要rem=ned-cnt个

不满足条件的有n-cnt个

我们需要交换已经满足条件的（即3的倍数）与不满足条件的进行交换每次交换会使满足条件的个数+1

由此可知，我们需要从不满足条件的个数中挑选出rem个与满足条件的进行交换，得到式子C(rem,cnt)*C(rem,n-cnt)(我的组合数好像写反了，那就反着来吧)此时得到的数量已经满足条件了，此时这就是好数列，但是我们需要求出所有情况，通过观察发现，我们单独对此时不满足条件的进行排列不会影响满足条件的个数，所有我们在×上A(n-cnt,n-cnt)（对所有不满足条件的进行全排列），然后我们还需要对原先满足条件的cnt个进行全排列（内部进行全排列，也不会影响满足条件的个数，不然会缺少情况）综上所述，得到式子ans=c(rem,cnt)*c(rem,n-cnt)*fac[n-cnt]*fac[cnt]（别忘记%mod）

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
int fac[1000007];
int fastpow(int x,int p){
    int ans=1;
    while(p){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
int inv(int x){
    return fastpow(x,mod-2);
}
int c(int x,int y){
    return fac[y]*inv(fac[x])%mod*inv(fac[y-x])%mod;
}
void solve(){
    int n;cin>>n;
    int cnt=n/3;//已经有cnt个了
    int ned=n/2;//需要有need个
    int rem=ned-cnt;//还需要remain个
    int ans=c(rem,cnt)*c(rem,n-cnt)%mod*fac[n-cnt]%mod*fac[cnt]%mod;
    cout<<ans%mod;

}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    fac[0]=1;
    for(int i=1;i<=1000000;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}