Submission #1781333


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int mod = 1777777777;
struct ModCombination {
  ModCombination(unsigned int n) : n(n), F(n + 1, 1), I(n + 1, 1) {
    for (int i = 1; i <= n; ++i) F[i] = 1ll * i * F[i - 1] % mod;
    for (long long i = mod - 2, j = F[n]; i; i >>= 1) {
      if (i & 1) I[n] = I[n] * j % mod;
      j = j * j % mod;
    }
    for (int i = n - 1; i; --i) I[i] = I[i + 1] * (i + 1ll) % mod;
  }

  unsigned int n;
  vector<int> F, I;

  int operator()(int p, int k) {
    if (p > n) exit(-1);
    if (k > p) return 0;
    return 1ll * F[p] * I[k] % mod * I[p - k] % mod;
  }
};

long long mod_pow(long long a, long long x, int p = 1e9 + 7) {
  long long ret = 1;
  for (long long i = 1ll << 60; i; i >>= 1) {
    ret *= ret;
    ret %= p;
    if (x & i) {
      ret *= a;
      ret %= p;
    }
  }

  return ret;
}

long long inv(long long n, int p = 1e9 + 7) {
  return mod_pow(n, p - 2, p);
}

int main() {
  long long n, k;
  cin >> n >> k;

  if (n >= mod) {
    cout << 0 << endl;
  }

  vector<long long> fact(k + 1, 1);
  for (int i = 1; i < fact.size(); ++i) {
    fact[i] *= i * fact[i - 1] % mod;
    fact[i] %= mod;
  }

  ModCombination mc(k);
  long long t = 0;
  for (int i = 0; i <= k; ++i) {
    t += (mc(k, i) * fact[k - i] % mod) * (i & 1 ? -1 : 1);
    t %= mod;
  }

  long long a = 1;
  for (int i = 0; i < k; ++i) {
    a *= n - i;
    a %= mod;
  }

  a *= inv(fact[k], mod);
  a %= mod;

  cout << a * t % mod << endl;
}

Submission Info

Submission Time
Task C - 高橋君、24歳
User Luzhiled
Language C++14 (GCC 5.4.1)
Score 40
Code Size 1553 Byte
Status WA
Exec Time 21 ms
Memory 7552 KB

Judge Result

Set Name small large
Score / Max Score 40 / 40 0 / 60
Status
AC × 15
AC × 16
WA × 11
Set Name Test Cases
small 00_small/small_00_sample1.txt, 00_small/small_00_sample2.txt, 00_small/small_00_sample3.txt, 00_small/small_00_sample4.txt, 00_small/small_01_rand_01.txt, 00_small/small_01_rand_02.txt, 00_small/small_01_rand_03.txt, 00_small/small_01_rand_05.txt, 00_small/small_01_rand_07.txt, 00_small/small_01_rand_08.txt, 00_small/small_01_rand_09.txt, 00_small/small_01_rand_10.txt, 00_small/small_01_rand_13.txt, 00_small/small_01_rand_14.txt, 00_small/small_01_rand_18.txt
large 00_small/small_00_sample1.txt, 00_small/small_00_sample2.txt, 00_small/small_00_sample3.txt, 00_small/small_00_sample4.txt, 00_small/small_01_rand_01.txt, 00_small/small_01_rand_02.txt, 00_small/small_01_rand_03.txt, 00_small/small_01_rand_05.txt, 00_small/small_01_rand_07.txt, 00_small/small_01_rand_08.txt, 00_small/small_01_rand_09.txt, 00_small/small_01_rand_10.txt, 00_small/small_01_rand_13.txt, 00_small/small_01_rand_14.txt, 00_small/small_01_rand_18.txt, 01_large/large_00_sample5.txt, 01_large/large_01_rand_01.txt, 01_large/large_01_rand_02.txt, 01_large/large_01_rand_03.txt, 01_large/large_01_rand_05.txt, 01_large/large_01_rand_07.txt, 01_large/large_01_rand_08.txt, 01_large/large_01_rand_09.txt, 01_large/large_01_rand_10.txt, 01_large/large_01_rand_13.txt, 01_large/large_01_rand_14.txt, 01_large/large_01_rand_18.txt
Case Name Status Exec Time Memory
00_small/small_00_sample1.txt AC 1 ms 256 KB
00_small/small_00_sample2.txt AC 1 ms 256 KB
00_small/small_00_sample3.txt AC 1 ms 256 KB
00_small/small_00_sample4.txt AC 1 ms 256 KB
00_small/small_01_rand_01.txt AC 1 ms 256 KB
00_small/small_01_rand_02.txt AC 1 ms 256 KB
00_small/small_01_rand_03.txt AC 1 ms 256 KB
00_small/small_01_rand_05.txt AC 1 ms 256 KB
00_small/small_01_rand_07.txt AC 1 ms 256 KB
00_small/small_01_rand_08.txt AC 1 ms 256 KB
00_small/small_01_rand_09.txt AC 1 ms 256 KB
00_small/small_01_rand_10.txt AC 1 ms 256 KB
00_small/small_01_rand_13.txt AC 1 ms 256 KB
00_small/small_01_rand_14.txt AC 1 ms 256 KB
00_small/small_01_rand_18.txt AC 1 ms 256 KB
01_large/large_00_sample5.txt AC 1 ms 256 KB
01_large/large_01_rand_01.txt WA 9 ms 3072 KB
01_large/large_01_rand_02.txt WA 17 ms 5760 KB
01_large/large_01_rand_03.txt WA 7 ms 2304 KB
01_large/large_01_rand_05.txt WA 21 ms 7424 KB
01_large/large_01_rand_07.txt WA 2 ms 384 KB
01_large/large_01_rand_08.txt WA 3 ms 896 KB
01_large/large_01_rand_09.txt WA 13 ms 4480 KB
01_large/large_01_rand_10.txt WA 4 ms 1152 KB
01_large/large_01_rand_13.txt WA 21 ms 7552 KB
01_large/large_01_rand_14.txt WA 11 ms 3712 KB
01_large/large_01_rand_18.txt WA 19 ms 6656 KB