結果

問題 No.1978 Permutation Repetition
ユーザー qwewe
提出日時 2025-05-14 13:18:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 5,778 bytes
コンパイル時間 1,106 ms
コンパイル使用メモリ 91,184 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:19:05
合計ジャッジ時間 2,627 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <vector> 
#include <utility> // For std::swap

// Define the modulus
const long long MOD = 1000000007;

// Function to compute (base^exp) % MOD using binary exponentiation
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Function to compute modular inverse using Fermat's Little Theorem
// Assumes MOD is prime and n is not a multiple of MOD
long long modInverse(long long n) {
    // Check if n is 0 modulo MOD, though this shouldn't happen for factorials unless N >= MOD
    if (n % MOD == 0) return 0; // Should handle this case if possible, but not expected here
    return power(n, MOD - 2);
}

// Function to compute GCD (Greatest Common Divisor) using Euclidean algorithm
// Handles non-negative inputs. Assumes a, b >= 0.
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Define MAXN based on problem constraints N <= 1000
const int MAXN = 1005; 
long long fact[MAXN];
long long invFact[MAXN];

// Precompute factorials and their modular inverses up to N
void precompute_factorials(int n) {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]); 
    }
}

// Function to compute combinations C(n, k) mod MOD using precomputed values
long long combinations(int n, int k) {
    // Check for invalid inputs
    if (k < 0 || k > n) {
        return 0;
    }
    // Compute C(n, k) = n! / (k! * (n-k)!) using modular inverses
    // C(n, k) = (n! * inv(k!)) % MOD * inv((n-k)!) % MOD
    long long res = (fact[n] * invFact[k]) % MOD;
    res = (res * invFact[n - k]) % MOD;
    return res;
}


int main() {
    // Use faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    long long M; // M can be large, up to 10^9
    std::cin >> N >> M;

    std::vector<int> A(N + 1); // Permutation A, 1-indexed
    for (int i = 1; i <= N; ++i) {
        std::cin >> A[i];
    }

    // Precompute factorials and their modular inverses up to N
    precompute_factorials(N);

    // Map to store counts of cycles by length: {length: count}
    std::map<int, int> cycle_len_counts;
    std::vector<bool> visited(N + 1, false); // Track visited elements

    // Find cycle decomposition of permutation A
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            int current = i;
            int count = 0; // Length of the current cycle
            // Traverse the cycle
            while (!visited[current]) {
                visited[current] = true;
                current = A[current];
                count++;
            }
            // Increment the count for cycles of this length
             cycle_len_counts[count]++;
        }
    }

    long long total_ans = 1; // Initialize total answer
    std::vector<long long> dp(N + 1); // DP table for computing contributions for each cycle length L

    // Iterate through each distinct cycle length L found in A and its count N_L
    for (auto const& [L_int, N_L] : cycle_len_counts) {
        long long L = (long long)L_int; // Use long long for L in calculations

        // Find the set S_L of valid group sizes k.
        // k is a valid group size if k divides M and gcd(M/k, L) = 1.
        std::vector<int> S_L;
        for (int k = 1; k <= N_L; ++k) { // k must be at least 1 and at most N_L
            if (M % k == 0) { // Check if k divides M
                 long long M_div_k = M / k; 
                 // Check the gcd condition. Use long long version of L.
                 if (gcd(M_div_k, L) == 1) {
                    S_L.push_back(k);
                 }
            }
        }

        // Dynamic programming calculation for N_L cycles of length L
        dp[0] = 1; // Base case: 0 cycles contribute 1 way (empty product)
        for (int i = 1; i <= N_L; ++i) { // Compute dp[i] for i cycles
            dp[i] = 0; // Initialize dp[i]
            // Iterate through all valid group sizes k in S_L
            for (int k : S_L) {
                if (k > i) continue; // Group size k cannot exceed current number of cycles i
                
                // Calculate N(k, L) = (k-1)! * L^(k-1) mod MOD
                // This is the number of ways to form P cycles from k cycles of A
                long long N_k_L;
                if (k == 1) {
                     N_k_L = 1; // (1-1)! * L^(1-1) = 0! * L^0 = 1 * 1 = 1
                } else {
                     // Calculate L^(k-1) mod MOD
                     long long L_pow_k_minus_1 = power(L, k - 1);
                     // N(k, L) = (k-1)! * L^(k-1)
                     N_k_L = (fact[k - 1] * L_pow_k_minus_1) % MOD;
                }

                // Calculate combinations C(i-1, k-1) mod MOD
                // This represents choosing k-1 cycles to group with a fixed cycle
                long long combinations_val = combinations(i - 1, k - 1);
                
                // Calculate the term for this k: C(i-1, k-1) * N(k, L) * dp[i-k] mod MOD
                long long term = (combinations_val * N_k_L) % MOD;
                term = (term * dp[i - k]) % MOD;
                
                // Add this term to dp[i]
                dp[i] = (dp[i] + term) % MOD;
            }
        }
        // Multiply the total answer by the result for this cycle length L
        total_ans = (total_ans * dp[N_L]) % MOD;
    }

    // Output the final computed answer
    std::cout << total_ans << std::endl;

    return 0;
}
0