/**
* Method: Recurrence relation. Coefficients of the recurrence are computed by
* generating the state diagram.
*
* Author: Catalin Francu
**/
#include <stdio.h>
#include <string.h>
#define MAX_VALUE 1000000
#define MOD 1000000007
#define MAX_STATES 13 /* determined experimentally */
#define MASK_SIZE 5 /* information about each state is stored on 5 bits */
typedef unsigned long long u64;
/* map of state mask (5-bit) to state number */
int stateMap[1 << MASK_SIZE];
int numStates;
/* for each state, store a list of its dependencies */
typedef struct {
int state;
int newBits;
int totalBits;
} recurrence;
recurrence coef[MAX_STATES][MAX_STATES];
int numCoefs[MAX_STATES];
/* frequencies of array elements */
int freq[MAX_VALUE + 1];
/* c[i][j] = ways of distributing the first i sets of distinct values while */
/* ending in state j. However, c[i] only depends on c[i - 1], so we only need */
/* to store two rows. */
int p[MAX_STATES], q[MAX_STATES];
int bitCount(int x) {
int result = 0;
while (x) {
result++;
x &= x - 1;
}
return result;
}
int validState(int s) {
return
((s & 0x3) != 0x1) && /* bit 0 may not appear before bit 1 */
((s & 0x18) != 0x10) && /* bit 4 may not appear before bit 3 */
(!(s & 0x4) || ((s & 0xa) == 0xa)); /* bit 2 may not appear before bits 1 and 3 */
}
int validTransition(int from, int to, int *newBits, int *totalBits) {
int add = ~from & to; /* appearing bits */
*newBits = bitCount(add);
*totalBits = bitCount(to);
if (add & 0x4) {
/* when adding bit 2, may not operate on bits 1 and 3 at the same time */
*totalBits -= 2;
} else if (from & 0x04) {
/* once bit 2 exists, may no longer operate on bits 1, 2 and 3 */
*totalBits -= 3;
}
return
!(from & ~to) && /* bits may not disappear */
!(add & (add >> 1)) && /* may not add consecutive bits at the same time */
*totalBits; /* must have some bits to operate on */
}
void computeStateMatrix() {
int newBits, totalBits;
for (int to = 0; to < (1 << MASK_SIZE); to++) {
if (validState(to)) {
stateMap[to] = numStates++;
for (int from = 0; from <= to; from++) {
if (validState(from) &&
validTransition(from, to, &newBits, &totalBits)) {
int sfrom = stateMap[from];
int sto = stateMap[to];
coef[sto][numCoefs[sto]++] = (recurrence) { sfrom, newBits, totalBits };
}
}
}
}
}
/* precomputing this can cut the running time by some 20% */
int choose(int n, int k) {
switch (k) {
case 0: return 1;
case 1: return n;
case 2: return (u64)n * (n - 1) / 2 % MOD;
case 3: return (u64)n * (n - 1) * (n - 2) / 6 % MOD;
default: return 0; /* should be unreachable */
}
}
/* combinations with repetition: how many ways are there of placing n */
/* identical balls into k non-identical urns? */
int chooseRep(int n, int k) {
return choose(n + k - 1, k - 1);
}
int main() {
/* read input data; we only care about element frequencies */
int n, x;
scanf("%d", &n);
while (n--) {
scanf("%d", &x);
freq[x]++;
}
computeStateMatrix();
p[0] = 1;
/* distribute groups of equal elements in increasing order */
for (int v = 1; v <= MAX_VALUE; v++) {
if (freq[v]) {
for (int st = 0; st < numStates; st++) {
u64 current = 0;
for (int i = 0; i < numCoefs[st]; i++) {
if (freq[v] >= coef[st][i].newBits) {
/* otherwise we cannot occupy all the new sequences as promised */
current += (u64)p[coef[st][i].state] *
chooseRep(freq[v] - coef[st][i].newBits, coef[st][i].totalBits);
}
}
q[st] = current % MOD;
}
memcpy(p, q, sizeof(q));
}
}
printf("%d\n", p[numStates - 1]);
}
Compilation message
w.c: In function 'main':
w.c:115:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^~~~~~~~~~~~~~~
w.c:117:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
256 KB |
Output is correct |
| 3 |
Correct |
13 ms |
256 KB |
Output is correct |
| 4 |
Correct |
38 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
256 KB |
Output is correct |
| 2 |
Correct |
6 ms |
376 KB |
Output is correct |
| 3 |
Correct |
21 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
53 ms |
4216 KB |
Output is correct |
| 5 |
Correct |
82 ms |
2296 KB |
Output is correct |
| 6 |
Correct |
143 ms |
4216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
256 KB |
Output is correct |
| 2 |
Correct |
6 ms |
256 KB |
Output is correct |
| 3 |
Correct |
6 ms |
256 KB |
Output is correct |
| 4 |
Correct |
6 ms |
256 KB |
Output is correct |
| 5 |
Correct |
7 ms |
376 KB |
Output is correct |
| 6 |
Correct |
7 ms |
376 KB |
Output is correct |
| 7 |
Correct |
9 ms |
760 KB |
Output is correct |
| 8 |
Correct |
23 ms |
632 KB |
Output is correct |
| 9 |
Correct |
32 ms |
376 KB |
Output is correct |
| 10 |
Correct |
149 ms |
4320 KB |
Output is correct |
