视频题解

https://www.bilibili.com/video/BV1GY4y1y7RA/?spm_id_from=333.999.0.0

思路

1.因为题目要求排序。所以最终相同长度的单词一定会聚拢在一起。所以分别对不同长度的单词求解，然后使用乘法原理，乘起来就好。

2.对于相同长度的单词，如果单词没有重复，则直接阶乘。但是题目没规定无重复，所以考虑对相同单词归类计数,然后进行可重复元素的排列。参考这里 .

举个例子:

a a b b aa bb ccc

先按长度分为:

a a b b

aa bb

ccc

长度为1： 答案为 4!/(2!∗2!)=64!/(2!∗2!)=6

长度为2： 答案为 2!/(1!∗1!)=22!/(1!∗1!)=2

长度为1： 答案为 1!/1!=11!/1!=1

总答案为: 6∗2∗1=126∗2∗1=12

实现细节：

由于题目需要我们求模意义下的取值，而且可重集的重排列又涉及到了除法 操作，所以我们需要使用费马小定理 来求逆元. $a^{−1}≡a^{m-2}(mod \ m)$

直接模拟显然不现实，这里我们使用快速幂来求$a^{m-2}$

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
// d 第一个维度按长度分类  第二个维度按单词分 
unordered_map<int,unordered_map<string,int>> d;
// 预处理阶乘
ll fac[300005];
// 快速幂，为了求逆元
ll ksm (ll a , ll b){
    ll ans = 1 , base = a;
    while (b){
        if (b & 1) ans = ans * base % mod;
        b >>= 1;
        base = base * base % mod;
    }
    return ans;
}
int main() {
    // 关闭同步流，加速读入
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        string a;
        cin >> a;
        d[a.size()][a] += 1;
    }
    // 预处理阶乘在mod意义下的取值
    fac[1] = 1;
    for (int i = 2 ; i <= 300000 ; i++)
        fac[i] = fac[i - 1] * i % mod;
    // 分长度求解
    ll ans = 1;
    for (auto & g : d){
        // 先求这个长度的总个数
        int tot = 0;
        for (auto & f : g.second) tot += f.second;
        // 求相同字符串，根据可重复排列，需要除掉。
        // 取模意义下的除法就是求逆元。使用费马小定理:a^(mod - 2) == a^-1 (mod prime)
        ll t = 1;
        for (auto & f : g.second) {
            t = t * ksm(fac[f.second] , mod - 2) % mod;
        }
        t = t * fac[tot] % mod;
        // 不同长度的答案，根据乘法原理，相乘即可
        ans = ans * t % mod;
    }
    cout << ans << endl;
	return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

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

        Map<Integer, Map<String, Integer>> d = new HashMap<>();
        long[] fac = new long[300005];

        for (int i = 1; i <= n; i++) {
            String a = scanner.next();
            d.computeIfAbsent(a.length(), k -> new HashMap<>()).merge(a, 1, Integer::sum);
        }

        fac[1] = 1;
        for (int i = 2; i <= 300000; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }

        long ans = 1;
        for (Map.Entry<Integer, Map<String, Integer>> entry : d.entrySet()) {
            int tot = entry.getValue().values().stream().mapToInt(Integer::intValue).sum();
            long t = 1;
            for (Map.Entry<String, Integer> f : entry.getValue().entrySet()) {
                t = t * modInverse(fac[f.getValue()], MOD) % MOD;
            }
            t = t * fac[tot] % MOD;
            ans = ans * t % MOD;
        }

        System.out.println(ans);
    }

    private static long modInverse(long a, int mod) {
        return ksm(a, mod - 2, mod);
    }

    private static long ksm(long a, long b, int mod) {
        long ans = 1;
        long base = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = ans * base % mod;
            }
            base = base * base % mod;
            b >>= 1;
        }
        return ans;
    }
}

Python

import sys
from collections import defaultdict

input_fn = lambda: sys.stdin.readline().strip()

MOD = 1000000000 + 7

def calculate_factorial(n):
    fab = [1] * (n + 1)
    for i in range(2, n + 1):
        fab[i] = (fab[i - 1] * i) % MOD
    return fab

def fast_power(a, b):
    ans = 1
    base = a
    while b:
        if b & 1:
            ans = (ans * base) % MOD
        base = (base * base) % MOD
        b = b >> 1
    return ans

def main():
    n = int(input_fn())
    words = input_fn().split()

    word_count_by_length = defaultdict(lambda: defaultdict(int))

    for word in words:
        word_count_by_length[len(word)][word] += 1

    MAXI = 100001
    factorial = calculate_factorial(MAXI)

    result = 1
    for length, count_by_word in word_count_by_length.items():
        total_count = 0
        product = 1

        for word, occurrence in count_by_word.items():
            total_count += occurrence
            product = (product * fast_power(factorial[occurrence], MOD - 2)) % MOD

        product = (product * factorial[total_count]) % MOD
        result = (result * product) % MOD

    print(result)

if __name__ == "__main__":
    main()

题目内容

小红是一名小学生，他非常喜欢玩文字游戏。有一天，他在家里发现了一些单词，这些单词的长度不同，但是他想要将它们按照单词长度进行排序。因为他非常聪明，所以他很快就想到了一个方法：对于同一个长度的单词，他可以任意安排它们的位置。于是，他开始了他的排序之旅。

现在小红拿到了一些单词， 他准备将这些单词按照单词长度进行非降序排序。对于同一个长度的单词，小红可以任意安排它们的位置。

小红想知道，最终有多少种不同的排序方式？由于答案可能过大，请对 $10^9+7$ 取模。

我们定义，如果两个方案排序后的字符串不同，则视为两种方案。

输入描述

第一行输入一个正整数 $n$ ，代表单词的数量。

第二行输入一行字符串，仅包含小写字母和空格。两个单词之间保证恰好有一个空格。

$1 \le n \le 100000$

所有单词的长度之和不超过 $300000$ 。

输出描述

最终的方案数对 $10^9 + 7$ 取模的值。

样例

样例一：

输入

3
tazi ta zi

输出

2