Submission #198434

#	Time	Username	Problem	Language	Result	Execution time	Memory
198434		model_code	W (RMI18_w)	C11	30 / 100	34 ms	2680 KiB

w

/**
 * Method: Summation by convolution for the case of N distinct elements.
 *
 * Author: Catalin Francu
 **/
#include <stdio.h>

#define MOD 1000000007
#define MAX_N 300000
#define NUM_WAYS 8

const int WAYS[NUM_WAYS][4] =
  {
   { 2, 1, 3, 1 },
   { 2, 1, 3, 2 },
   { 2, 4, 3, 1 },
   { 2, 4, 3, 2 },
   { 2, 4, 3, 1 },
   { 2, 4, 3, 2 },
   { 2, 4, 2, 1 },
   { 2, 4, 2, 1 },
  };

typedef unsigned long long u64;

u64 p[MAX_N];

int main() {
  /* read input data; we only care about n */
  int n;
  scanf("%d", &n);

  u64 result = 0;
  for (int way = 0; way < NUM_WAYS; way++) {
    u64 sum = 1;
    u64 pow = 1;
    for (int i = 2; i < n - 2; i++) {
      /* here i is the current position of C and sum is the number of ways to */
      /* distribute the elements to the left of C */
      p[i] = sum;
      pow = (pow * WAYS[way][1]) % MOD;
      sum = (sum * WAYS[way][0] + pow) % MOD;
    }

    sum = 1;
    pow = 1;
    for (int i = 2; i < n - 2; i++) {
      /* here i is the current position of C, sum is the number of ways to */
      /* distribute the elements to the right of C, and the convolution of p[] */
      /* and sum is added to the final result. */
      result = (result + sum * p[n - 1 - i]) % MOD;
      pow = (pow * WAYS[way][3]) % MOD;
      sum = (sum * WAYS[way][2] + pow) % MOD;
    }
  }

  /* there are 16 states and we handled 8, so take symmetry into account */
  result = result * 2 % MOD;

  printf("%llu\n", result);
}

Compilation message (stderr)

w.c: In function 'main':
w.c:31:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ^~~~~~~~~~~~~~~

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