Challenge: Cycle Representation
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775637
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/cycle-representation/problem
Cerinta
Let $n$ be a fixed integer. <br>
A **permutation** is a bijection from the set $\{1,2,\ldots,n\}$ to itself. <Br><br>
A **cycle of length $k$** ($k\ge 2$) is a permutation $f$ where different integers exist $i_1,\ldots,i_k$ such that $f(i_1)=i_2, f(i_2)=i_3, \ldots, f(i_k)=i_1$ and, for all $x$ not in $\{i_1,\ldots,i_k\}$, $f(x)=x$.
The **composition of $m$ permutations** $f_1,\ldots,f_m$, written $f_1\circ f_2\circ\ldots\circ f_m$, is their composition as functions.
Steve has some cycles $f_1,f_2,\ldots,f_m$. He knows the length of cycle $f_i$ is $l_i$, but he does not know exactly what the cycles are.
He finds that the composition $f_1\circ f_2\circ\ldots\circ f_m$ of the cycles is a cycle of length $n$. <br>
He wants to know how many possibilities of $f_1,\ldots,f_m$ exist.Input Format
The first line contains $T$, the number of test cases. <br>
Each test case contains the following information:<br>
The first line of each test case contains two space separated integers, $n$ and $m$.<br>
The second line of each test case contains $m$ integers, $l_1,\ldots,l_m$.
**Constraints**
$n \geqslant 2$
Sum of $n\leqslant 1000$
$2\leqslant l_i \leqslant n$
Sum of $m\le 10^6$Output Format
Output $T$ lines. Each line contains a single integer, the answer to the corresponding test case.
Since the answers may be very large, output them modulo $(10^9+7)$.Cod sursa
#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;
}
HackerRank Combinatorics – Cycle Representation