結果
問題 |
No.665 Bernoulli Bernoulli
|
ユーザー |
![]() |
提出日時 | 2019-07-20 11:18:22 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,087 bytes |
コンパイル時間 | 1,357 ms |
コンパイル使用メモリ | 31,872 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-29 17:25:32 |
合計ジャッジ時間 | 2,382 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
ソースコード
// yukicoder: No.665 Bernoulli Bernoulli // 2019.7.20 bal4u #include <stdio.h> typedef long long ll; const int M = 1000000007; int powmod(int b, int p) { int r = 1; while (p) { if (p & 1) r = (ll)r * b % M; b = (ll)b * b % M; p >>= 1; } return r; } int egcd(int a, int b, int *x, int *y) { int d; if (b == 0) { *x = 1; *y = 0; return a; } d = egcd(b, a % b, y, x); *y -= a / b * (*x); return d; } int inv(int a) { int x, y; egcd(a, M, &x, &y); return x % M; } int fact[10005] = {1}; int xpow[10005]; int main() { int i, N, K, K1, ans; { ll _; scanf("%lld%d", &_, &K), N = (int)(_ % M), K1 = K+1; } for (i = 1; i <= K1; i++) { fact[i] = (ll)fact[i-1]*i % M; xpow[i] = (xpow[i-1] + powmod(i, K)) % M; } if (N <= K1) { printf("%d\n", xpow[N]); return 0; } ans = 0; for (i = 1; i <= K1; i++) { ll t = (ll)xpow[i] * inv((ll)fact[i]*fact[K1-i] % M * (N-i) % M); if (!((i&1) ^ (K&1))) t = -t; ans = (t + ans) % M; } for (i = N-K1; i <= N; i++) ans = (ll)ans*i % M; if (ans < 0) ans += M; printf("%d\n", ans); return 0; }