Submission #198432

#	Time	Username	Problem	Language	Result	Execution time	Memory
198432		model_code	W (RMI18_w)	C11	100 / 100	149 ms	4344 KiB

w

/**
 * 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 (stderr)

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);
     ^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50