結果

問題 No.823 Many Shifts Easy
ユーザー akakimidoriakakimidori
提出日時 2019-06-06 11:18:55
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 1,473 bytes
コンパイル時間 938 ms
コンパイル使用メモリ 32,964 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-25 08:06:55
合計ジャッジ時間 1,387 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 6 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 4 ms
4,348 KB
testcase_06 AC 5 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 5 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>
#include<math.h>

typedef int32_t i32;
typedef int64_t i64;

const i32 mod = 1000000007;

i32 inv (i32 a) {
  i32 t = 1;
  while (a > 1) {
    t = (i64) t * (mod - mod / a) % mod;
    a = mod % a;
  }
  return t;
}

i32 mod_pow (i32 r, i32 n) {
  i32 t = 1;
  i32 s = r;
  while (n > 0) {
    if (n & 1) t = (i64) t * s % mod;
    s = (i64) s * s % mod;
    n >>= 1;
  }
  return t;
}

i32 *fact = NULL;
i32 *iFact = NULL;
void init_fact (const i32 n) {
  fact = (i32 *) calloc (n + 1, sizeof (i32));
  fact[0] = 1;
  for (i32 i = 1; i <= n; ++i) {
    fact[i] = (i64) i * fact[i - 1] % mod;
  }
  iFact = (i32 *) calloc (n + 1, sizeof (i32));
  iFact[n] = inv (fact[n]);
  for (i32 i = n - 1; i >= 0; --i) {
    iFact[i] = (i64) (i + 1) * iFact[i + 1] % mod;
  }
}

i32 perm (i32 n, i32 k) {
  if (!(0 <=k && k <= n)) return 0;
  return (i64) fact[n] * iFact[n - k] % mod;
}

i32 comb (i32 n, i32 k) {
  if (!(0 <= k && k <= n)) return 0;
  return (i64) fact[n] * iFact[k] % mod * iFact[n - k] % mod;
}

void run (void) {
  i32 n, k;
  scanf ("%" SCNi32 "%" SCNi32, &n, &k);
  init_fact (n + k);
  i32 ans = 0;
  for (i32 i = 1; i <= n; ++i) {
    ans = (ans + (i64) i * perm (n - 1, k)) % mod;
    if (i < n) {
      ans = (ans + (i64) i * comb (k, 2) % mod * perm (n - 2, k - 2)) % mod;
    }
  }
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}
0