結果
問題 | No.573 a^2[i] = a[i] |
ユーザー |
![]() |
提出日時 | 2016-12-26 14:56:45 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 2,417 ms |
コンパイル使用メモリ | 55,956 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-15 00:04:00 |
合計ジャッジ時間 | 2,851 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#include <iostream> #define int long long using namespace std; int mod = 1000000007; //素数 int n; int fact[100001]; //fact[n] = n! % mod //a^n % modを返す, 前処理は不要なのでmodは引数にしてよい。 int powmod(int a, int n, int mod) { if (n == 0) return 1; if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod) % mod; return (a * powmod(a, n - 1, mod)) % mod; } //nCk % modを返す (factを前処理で求めてる必要あり。modが変わればfactも更新) int comb(int n, int k) { if (k > n) return 0; int a = fact[n]; int b = powmod(fact[k], mod - 2, mod); //(k! * b) % mod = 1となる整数b. bはk!の逆元という。 int c = powmod(fact[n - k], mod - 2, mod); //任意の正整数x, y(x % y == 0)と素数pについて、(x / y) % p = (x * y^(p-2)) % pが成り立つことを利用している。(フェルマーの小定理) return (((a * b) % mod) * c) % mod; } signed main() { int i; cin >> n; fact[0] = 1; for (i = 1; i <= n; i++) fact[i] = (i * fact[i - 1]) % mod; int ans = 0; for (i = 1; i <= n; i++) { ans += comb(n, i) * powmod(i, n - i, mod); ans %= mod; } cout << ans << endl; return 0; }