We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Cycle Representation
  5. Discussions

Cycle Representation

Sort by

recency

|

3 Discussions

|

  • TChalla
     + 0 comments

    C++ solution

    #include <bits/stdc++.h>

using namespace std;

#define int64 unsigned long long int

int64 prime = 1000000007ULL;
int64 bin[1001][1001];
int64 binsum[1001][1001];
int cs[1001][1001];

int64 power(int64 abase, int64 aexp){
    int64 base = abase;
    int64 exp = aexp;
    int64 res=1;
    while(exp > 0ULL){
       if(exp % 2ULL == 1ULL) res = (res * base) % prime;
       base = (base * base) % prime;
       exp /= 2ULL;
    }
    return res % prime;
}

int64 fast_chi(int n, int m, int c){
    if(c == n){
        if((m + 1) % 2 == 0) return 1ULL;
        else return (prime - 1ULL);       
    }
    else{
        int lower_limit;
        int upper_limit;
        if((c <= m) && (c <= (n - m + 1))){
            lower_limit = 1;
            upper_limit = c;
        }
        else if((c > m) && (c <= (n - m + 1))){
            lower_limit = 1;
            upper_limit = m;
        }
        else if((c <= m) && (c > (n - m + 1))){
            lower_limit = c - (n - m);
            upper_limit = c;
        }
        else{
            lower_limit = c - (n - m);
            upper_limit = m;
        }
        int64 lower_sum = 0ULL;
        int64 upper_sum = 0ULL;
        int64 answer;
        for(int x = lower_limit; x < (upper_limit + 1); x += 2) 
            lower_sum = (lower_sum + bin[n - c][m - x]) % prime;
        if(lower_limit < upper_limit) 
            for(int x = lower_limit+1; x < (upper_limit + 1); x += 2) 
                upper_sum = (upper_sum + bin[n - c][m - x]) % prime;
        if((lower_limit + 1) % 2 == 0) 
            answer = (lower_sum + ((upper_sum * (prime - 1)) % prime)) % prime;
        else answer = (upper_sum + ((lower_sum * (prime - 1)) % prime)) % prime;         
        int64 banswer = binsum[n - c][m - lower_limit];
        if(upper_limit < m) 
            banswer += (((prime - 1) * binsum[n - c][m - upper_limit - 1]) % prime);
        if(m % 2 == 0) banswer = (banswer * (prime - 1)) % prime;
        return banswer;
    }
}

int64 chi(int n, int m, int c){
    if(2 * m < (n + 1)){
        if(c == 1) return bin[n - 1][m - 1];
        else if(c <= m){
            int64 total = 0ULL;
            for(int i = 0; i < c; i++){
                int x = i + 1;
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else if((c > m) && (c <= (n - m + 1))){
            int64 total = 0ULL;
            for(int i = 0; i < m; i++){
                int x = i + 1;
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else if((c > (n - m + 1)) && (c < n)){
            int64 total = 0ULL;
            for(int x = c - (n - m); x < (m + 1); x++){
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else{
            if((m + 1) % 2 == 0) return 1ULL;
            else return (prime - 1ULL);
        }
    }
    else{
        if(c == 1) return bin[n - 1][m - 1];
        else if(c <= (n - m + 1)){
            int64 total = 0ULL;
            for(int i = 0; i < c; i++){
                int x = i + 1;
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else if((c > (n - m + 1)) && (c <= m)){
            int64 total = 0ULL;
            for(int x = c - (n - m); x < (c + 1); x++){
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else if((c > m) && (c < n)){
            int64 total = 0ULL;
            for(int x = c - (n - m); x < (m + 1); x++){
                if((x + 1) % 2 == 0) total = (total + bin[n - c][m - x]) % prime;
                else{
                    int64 add = (bin[n - c][m - x] * (prime - 1ULL)) % prime;
                    total = (total + add) % prime;
                }
            }
            return total;
        }
        else{
            if((m + 1) % 2 == 0) return 1ULL;
            else return (prime - 1ULL);
        }        
    }
}

int64 get_trace(int n, int m, int trial){
    int64 total = 1;
    int64 len_c = 0ULL;
    for(int i = 0; i < 1001; i++){
        int exponent = cs[trial][i];
        if(exponent > 0){
            int64 base = fast_chi(n, m, i);
            int64 ull_exp = (int64) exponent;
            len_c += ull_exp;
            int64 multiplier = power(base, ull_exp);
            total = (total * multiplier) % prime;
        }
    }
    int64 dimension = fast_chi(n, m, 1);
    total = (total * dimension) % prime;
    total = (total * chi(n, m, n)) % prime;
    int64 divisor = power(dimension, len_c);
    total = (total * power(divisor, prime-2)) % prime;
    return total;
}

int64 get_conjugacy_class_size(int n, int c){
    if(c == 1) return 1ULL;
    else{
        int64 total = bin[n][c];
        for(int i = 1; i < c; i++){
            int64 multiplier = (int64) i;
            total = (total * multiplier) % prime;
        }
        return total;
    }
}

int64 get_multiplier(int n, int trial){
    int64 long_n = (int64) n;
    int64 answer = power(long_n, prime - 2ULL);
    for(int i = 0; i < 1001; i++){
        int exponent = cs[trial][i];
        if(exponent > 0){
            int64 long_exp = (int64) exponent;
            int64 base = get_conjugacy_class_size(n, i);
            answer = (answer * power(base, long_exp)) % prime;
        }
    }
    return answer;
}

int64 get_enumeration(int n, int trial){
    int64 total = 0ULL;
    for(int i = 1; i < (n + 1); i++) total = (total + get_trace(n, i, trial)) % prime;
    int64 mult = get_multiplier(n, trial); total = (total * mult) % prime;
    return total;
}

int main(){
    int T; cin >> T;
    for(int i = 0; i < T; i++) 
        for(int j = 0; j < T; j++) 
            cs[i][j] = 0;
    int ns[T]; int ms[T];
    for(int i = 0; i < T; i++){
        int m; cin >> ns[i] >> m; ms[i] = m;
        for(int j = 0; j < m; j++){
            int k; cin >> k;
            cs[i][k] += 1;
        }
    }
    int max_n = 0;
    for(int i = 0; i < T; i++) if(ns[i] > max_n) max_n = ns[i];
    for(int i = 0; i < (max_n + 1); i++){
        for(int j = 0; j < (i + 1); j++){
            if(j ==0) bin[i][j] = 1ULL;
            else if(j == i) bin[i][j] = 1ULL;
            else bin[i][j] = (bin[i - 1][j] + bin[i - 1][j - 1]) % prime;
        }
    }
    for(int i = 0; i < (max_n + 1); i++){
        for(int j = 0; j < (i + 1); j++){
            if(j ==0) binsum[i][j] = 1ULL;
            else {
                int64 adder;
                if(j % 2 == 0) adder = bin[i][j];
                else adder = (bin[i][j] * (prime - 1)) % prime;
                binsum[i][j] = (binsum[i][j-1] + adder) % prime;
            }
        }
    }   
    for(int i = 0; i < T; i++){
        int64 answer = get_enumeration(ns[i], i);
        cout << answer << endl;
    }
    return 0;    
}

  • rouillai
     + 0 comments

    Quite interesting and valuable update for the students to avail the programming solutions. I truly admire the best essay writing service in usa help here that would be wise. Please continue with your further helping material please do share more.

  • robibhat
     + 1 comment

    When i submit my code it continuously says it is processing. It never shows a timed out symbol or a wrong answer symbol. What's going on?

No more comments