首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列

热度指数：2187 时间限制：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\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

在一行上输入一个正偶数  代表排列中的元素数量。

输出描述:

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

输出

说明

在这个样例中，长度为  的排列有且仅有两个：
，第一个元素  使得 ，第二个元素  使得 ，均不是  的倍数；
，同理。
因此，长度为  的排列中，不存在好排列。

示例2

输入

输出

说明

在这个样例中，一共有  个长度为  的排列满足条件，例如：
，第一个元素  使得 ，第二个元素  使得 ，第三个元素  使得 ，第四个元素  使得 ，恰好有一半的  使得  是  的倍数。

算法知识视频讲解

牛客313号_光

input()

print(0)

发表于 2025-07-05 18:21:09 回复(0)

牛客298721346号

乍一看象是很复杂的遍历问题，但内核其实更接近排列数&组合数的求解。这是数学题（雾）。

发表于 2025-05-24 23:05:23 回复(0)

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号

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)

C++

牛客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)

提交观点

问题信息

数论

难度：

6条回答 33收藏 242浏览

小红的好排列

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题