Submission #198431

#	Time	Username	Problem	Language	Result	Execution time	Memory
198431		model_code	W (RMI18_w)	C11	100 / 100	135 ms	4216 KiB

w

/**
 * Method: Recurrence relation. Coefficients of the recurrence are defined
 * manually by looking at the state diagram.
 *
 * Author: Catalin Francu
 **/
#include <stdio.h>

#define MAX_VALUE 1000000
#define MOD 1000000007

typedef unsigned long long u64;

typedef struct {
  u64 a, b, c, d, e, f, g, h, i;
} row;
row p, q;

/* frequencies of array elements */
int freq[MAX_VALUE + 1];

/* 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);
}

u64 helper(int value, int newBits, int totalBits, int freq) {
  return (freq >= newBits)
    ? (u64)value * chooseRep(freq - newBits, totalBits)
    : 0;
}

int main() {
  /* read input data; we only care about element frequencies */
  int n, x;
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &x);
    freq[x]++;
  }

  p.a = 1;

  for (int v = 1; v <= MAX_VALUE; v++) {
    if (freq[v]) {

      q.a = 0;
      q.b = (helper(p.a, 1, 1, freq[v]) +
             helper(p.b, 0, 1, freq[v])) % MOD;
      q.c = (helper(p.b, 1, 2, freq[v]) +
             helper(p.c, 0, 2, freq[v])) % MOD;
      q.d = (helper(p.a, 2, 2, freq[v]) +
             helper(p.b * 2, 1, 2, freq[v]) +
             helper(p.d, 0, 2, freq[v])) % MOD;
      q.e = (helper(p.b, 2, 3, freq[v]) +
             helper(p.c, 1, 3, freq[v]) +
             helper(p.d, 1, 3, freq[v]) +
             helper(p.e, 0, 3, freq[v])) % MOD;
      q.f = (helper(p.d, 1, 1, freq[v])) % MOD;
      q.g = (helper(p.d, 2, 2, freq[v]) +
             helper(p.e, 1, 2, freq[v]) +
             helper(p.f, 1, 1, freq[v]) +
             helper(p.g, 0, 1, freq[v])) % MOD;
      q.h = (helper(p.d, 2, 4, freq[v]) +
             helper(p.e * 2, 1, 4, freq[v]) +
             helper(p.h, 0, 4, freq[v])) % MOD;
      q.i = (helper(p.d, 3, 3, freq[v]) +
             helper(p.e * 2, 2, 3, freq[v]) +
             helper(p.f, 2, 2, freq[v]) +
             helper(p.g * 2, 1, 2, freq[v]) +
             helper(p.h, 1, 3, freq[v]) +
             helper(p.i, 0, 2, freq[v])) % MOD;

      p = q;
    }
  }

  printf("%llu\n", p.i);
}

Compilation message (stderr)

w.c: In function 'main':
w.c:48:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ^~~~~~~~~~~~~~~
w.c:50: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