Submission #198433

#	Time	Username	Problem	Language	Result	Execution time	Memory
198433		model_code	W (RMI18_w)	C11	30 / 100	8 ms	380 KiB

w

/**
 * Method: Direct formula for the case of all distinct elements.
 *
 * Author: Catalin Francu
 **/
#include <stdio.h>

#define MOD 1000000007
#define HALF 500000004 /* inverse of 2 modulo MOD */

typedef unsigned long long u64;

u64 power(int a, int n) {
  u64 result = 1;
  while (n--) {
    result = result * a % MOD;
  }
  return result;
}

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

  /* result = 2^(2 * n - 3) - n * 2^(n - 2) - (3^n + 7) / 2 + n + 6 * 2^(n - 2) */
  u64 x = power(2, n - 2);
  u64 y = power(3, n);
  u64 result = (2 * x * x % MOD
                + (MOD - n * x % MOD)
                + (MOD - HALF * (y + 7) % MOD)
                + n + 6 * x
                ) % MOD;

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

Compilation message (stderr)

w.c: In function 'main':
w.c:24: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