結果

問題 No.573 a^2[i] = a[i]
ユーザー startcpp
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0