首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列
  • 热度指数：3440 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红认为一个偶数长度为 n 的排列 \{a_1,a_2,\dots,a_n\} 是好排列，当且仅当恰好有一半的 i 使得 a_i \times i 是 3 的倍数。
\hspace{15pt}小红想知道，全部长度为 n 的排列中，共有多少个好排列？由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

\hspace{15pt}长度为 n 的排列是由 1 \sim n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，\{2,3,1,5,4\} 是一个长度为 5 的排列，而 \{1,2,2\} 和 \{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:
\hspace{15pt}在一行上输入一个正偶数 n \left(2 \leqq n \leqq 10^6\right) 代表排列中的元素数量。


输出描述:
\hspace{15pt}输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

2

输出

0

说明

\hspace{15pt}在这个样例中，长度为 2 的排列有且仅有两个：
\hspace{23pt}\bullet\,\{1,2\}，第一个元素 1 使得 1 \times 1 = 1，第二个元素 2 使得 2 \times 2 = 4，均不是 3 的倍数；
\hspace{23pt}\bullet\,\{2,1\}，同理。
\hspace{15pt}因此，长度为 2 的排列中，不存在好排列。
示例2

输入

4

输出

18

说明

\hspace{15pt}在这个样例中，一共有 18 个长度为 4 的排列满足条件，例如：
\hspace{23pt}\bullet\,\{1,2,4,3\}，第一个元素 1 使得 1 \times 1 = 1，第二个元素 2 使得 2 \times 2 = 4，第三个元素 4 使得 4 \times 3 = 12，第四个元素 3 使得 3 \times 4 = 12，恰好有一半的 i 使得 a_i \times i 是 3 的倍数。
算法知识视频讲解
添加回答
pandaC222头像 pandaC222

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

我们知道我们需要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;
}

发表于 2026-02-01 14:01:43 回复(0)
C++
牛客758963601号头像 牛客758963601号 
#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;

long long fact[MAX], inv_fact[MAX];

// 快速幂取模
long long pow_mod(long long x, int n) {
    long long res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

// 预处理阶乘和逆元
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[MAX-1] = pow_mod(fact[MAX-1], MOD-2);
    for (int i = MAX-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

// 组合数计算
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    precompute();
    int n;
    cin >> n;
    int k = n / 3;
    int s = n / 2 - k;
    int m = n - k;
    
    if (s < 0 || s > k || s > m) {
        cout << 0 << endl;
        return 0;
    }
    
    long long c = comb(m, s);
    long long perm1 = fact[k] * inv_fact[k - s] % MOD;
    long long perm2 = fact[k] * inv_fact[s] % MOD;
    long long ans = c * perm1 % MOD;
    ans = ans * perm2 % MOD;
    ans = ans * fact[n - k] % MOD;
    
    cout << ans << endl;
    return 0;
}

发表于 2025-03-04 21:10:30 回复(0)
Python3
Chinry头像 Chinry 
n=int(input())
MOD=10**9+7
def A(m,n):
    result=1
    for i in range(n-m+1,n+1):
        result=result*i % MOD
    return result
if n==2:
    print('0')
else:
    print(A(2*(n//3)-n//2,n//3)**2*A(n//2-n//3,n-n//3)*A(n-3*(n//3)+n//2,n-n//3)%MOD)

这题是真考数论，简化也是真的难简化。
大致思路拆解如下：
1、放在索引为3i位置的3x在全部3x中的组合：C(2*(n//3)-n//2   n//3)
2、放置3x数的3i索引在全部3i索引中的组合：C(2*(n//3)-n//2   n//3)
3、确定放置在3i索引的3x数（受1限制）在确定放置3x数的3i索引（受2限制）上的排列组合：A(2*(n//3)-n//2  2*(n//3)-n//2)
4、剩下的非3x的数字需要放置在剩下3i索引（受2限制）中的组合：C(n//2-n//3  n-n//3)
5、确定放在剩下3i索引（受2限制）的非3x数字（受4限制）在索引上的排列组合：A(n//2-n//3  n//2-n//3)
6、剩下所有数字（受1 4影响）直接进行排列组合：A(n-n//3  n-n//3)
六个乘起来就是了，然后化简到分母为1为止（也就是只有A存在）
发表于 2025-12-27 17:12:26 回复(0)
牛客313号_光头像 牛客313号_光
input()
print(0)

发表于 2025-07-05 18:21:09 回复(0)
牛客298721346号头像 牛客298721346号
乍一看象是很复杂的遍历问题，但内核其实更接近排列数&组合数的求解。这是数学题（雾）。
发表于 2025-05-24 23:05:23 回复(0)
SeptVir19头像 SeptVir19 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        long n = in.nextLong();
        long n_3 = n / 3; //99181
        long n_2 = n / 2; //148772 - 99181 = 49591

        if(n == 2) {
            System.out.println(0);
            return;
        }

        // res = A(n-n/3, n-n/3) * A(n/3, n/3) * C(n/3, n/2-n/3) * C(n-n/3, n/2-n/3)
        // int res =  (A(n-n_3, n-n_3) * A(n_3, n_3) * C(n_3, n_2-n_3) * C(n-n_3, n_2-n_3)) % mod;
        long res = A(n-n_3, n-n_3) * A(n_3, n_3) % mod;
        // System.out.println(res);
        // System.out.println("C "+ n_3 + " " + (n_2-n_3) + " :"  + C(99181, 49591));
        res = res * C(n_3, n_2-n_3) % mod;
        res = res * C(n-n_3, n_2-n_3) % mod;

        System.out.println(res);

    }

    static long A(long n, long m){
        long res = 1;
        for(long i=n-m+1; i <=n; i++){
            res = res * i % mod;
        }
        return res;
    }

    // 快速幂算法，计算 x^y % MOD
    private static long modPow(long x, long y, long mod) {
        long result = 1;
        x = x % mod;
        while (y > 0) {
            if ((y & 1) == 1) {
                result = (result * x) % mod;
            }
            y = y >> 1;
            x = (x * x) % mod;
        }
        return result;
    }

        // 计算阶乘的逆元
    private static long modInverse(long fact, long mod) {
        return modPow(fact, mod - 2, mod);
    }

    // 计算组合数 C(n, m) % MOD
    public static long C(long n, long m) {
        if (m > n) return 0;
        if (m == 0 || m == n) return 1;

        long[] fact = new long[(int) n + 1];
        fact[0] = 1;

        // 预处理阶乘
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % mod;
        }

        // 计算逆元
        long invM = modInverse(fact[(int) m], mod);
        long invNM = modInverse(fact[(int) (n - m)], mod);

        // 计算组合数
        return (fact[(int) n] * invM % mod * invNM % mod) % mod;
    }

}
解=非3n位置的所有数全排列 * 3n位置的所有数全排列 * 非3n位置中取n/2-n/3个位置 * 3n位置中取n/2-n/3个位置。
```res = A(n-n/3, n-n/3) * A(n/3, n/3) * C(n-n/3, n/2-n/3) * C(n/3, n/2-n/3)```
n/2-n/3个位置是相互交换的位置
发表于 2025-04-21 18:06:00 回复(0)
Java
牛客872422945号头像 牛客872422945号 
import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static int maxN = (int) 1e6;
    static long[] fact;
    static long[] finv;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        preprocess(maxN);

        int c = n / 3;
        int m = c;

        if (c > n / 2) {
            System.out.println(0);
            return;
        }

        int s = (n / 2) - c;
        if (m < s) {
            System.out.println(0);
            return;
        }

        int k = 2 * c - (n / 2);
        if (k < 0) {
            System.out.println(0);
            return;
        }

        int nc = n - c;
        int nm = n - m;
        int ck = c - k;
        int mk = m - k;

        long ans = comb(c, k);
        ans = ans * comb(nc, s) % MOD;
        ans = ans * (perm(m, k) * perm(nm, ck) % MOD) % MOD;
        ans = ans * (perm(mk, s) * fact[n / 2] % MOD) % MOD;

        System.out.println(ans);
    }

    static void preprocess(int n) {
        fact = new long[n + 1];
        finv = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        finv[n] = pow(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) {
            finv[i] = finv[i + 1] * (i + 1) % MOD;
        }
    }

    static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    static long comb(int a, int b) {
        if (a < 0 || b < 0 || a < b) return 0;
        return fact[a] * finv[b] % MOD * finv[a - b] % MOD;
    }

    static long perm(int a, int b) {
        if (a < 0 || b < 0 || a < b) return 0;
        return fact[a] * finv[a - b] % MOD;
    }
}

发表于 2025-04-03 15:12:38 回复(0)
求你们别卷了的鲸鱼很想减肥头像 求你们别卷了的鲸鱼很想减肥
count =0 def fact(n): sum = 1 for i in range(1,n+1): sum *= i return sum def fact1(n,m): sum = fact(n)//(fact(m)*fact(n-m)) return sum a=[i for i in range(1,int(input('输入一个偶数'))+1)] for i in a: if i%3==0: count += 1 s = int(count*2-len(a)//2) sum1 = fact(len(a)-count)*fact(count) sum2 =0 if s==0: sum2 = fact1(len(a)-count,count) else: for i in range(1,s+2): sum2 += (fact1(len(a)-count,i)*fact1(count,i)) print(sum2) print(sum1*sum2) print(((sum1*sum2)**len(a))%(10**9+7))
编辑于 2025-03-18 21:25:50 回复(0)
提交观点

问题信息

数论
难度：
8条回答 334浏览

热门推荐

相关试题

小红的好排列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号