結果

問題 No.573 a^2[i] = a[i]
コンテスト
ユーザー @abcde
提出日時 2019-03-17 18:39:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 5,178 bytes
コンパイル時間 1,164 ms
コンパイル使用メモリ 158,448 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 13:32:57
合計ジャッジ時間 3,092 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

// Submission #2145910
// https://abc066.contest.atcoder.jp/submissions/2145910
const LL MOD = 1e9 + 7;
LL F[111111];
LL IF[111111];

// Fermat's little theorem を 適用するため, ap-2乗 などを計算できるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL pow(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 配列 IF に, 逆元を保存.
// @param: 特に無し.
// @return: 配列IF の update.
void inverse(){
    F[0] = 1;
    IF[0] = 1;
    FOR(i, 1, 110001) {
        F[i] = (F[i-1] * i) % MOD;
        //逆元を、フェルマーの小定理を利用して求める
        IF[i] = pow(F[i], MOD - 2) % MOD;
    }
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列F, IF は, 事前に計算済のものを使う.
// @param P_: 対象となる要素の個数.
// @param Q_: 選択する要素の個数.
// @return:  組み合わせ(nCk)の計算結果.
LL comb(LL P_, LL Q_){
    if(P_ < 0 || Q_ < 0 || Q_ > P_) return 0;
    LL ret = F[P_] * IF[Q_] % MOD * IF[P_ - Q_] % MOD;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    inverse();
    LL N;
    cin >> N;
    
    // 2. 場合の数を計算.
    // ex.
    // N = 4 だと, 41通り(0 0 0 0 ～ 3 3 3 3) あるっぽい.
    // for(int i = 0; i < 4; i++){
    //     for(int j = 0; j < 4; j++){
    //         for(int k = 0; k < 4; k++){
    //             for(int l = 0; l < 4; l++){
    //                 int a[4] = {i, j, k, l};
    //                 bool ok = true;
    //                 for(int idx = 0; idx < 4; idx++) if(a[a[idx]] != a[idx]) ok = false;
    //                 if(ok) for(int idx = 0; idx < 4; idx++) cout << a[idx] << " ";
    //                 if(ok) cout << endl;
    //             }
    //         }
    //     }
    // }
    // N = 5 だと, 196通り(0 0 0 0 0 ～ 4 4 4 4 4) あるっぽい.
    // for(int i = 0; i < 5; i++){
    //     for(int j = 0; j < 5; j++){
    //         for(int k = 0; k < 5; k++){
    //             for(int l = 0; l < 5; l++){
    //                 for(int m = 0; m < 5; m++){
    //                     int a[5] = {i, j, k, l, m};
    //                     bool ok = true;
    //                     for(int idx = 0; idx < 5; idx++) if(a[a[idx]] != a[idx]) ok = false;
    //                     if(ok) for(int idx = 0; idx < 5; idx++) cout << a[idx] << " ";
    //                     if(ok) cout << endl;
    //                 }
    //             }
    //         }
    //     }
    // }
    // N = 6 だと, 1057通り(0 0 0 0 0 0 ～ 5 5 5 5 5 5) あるっぽい.
    // for(int i = 0; i < 6; i++){
    //     for(int j = 0; j < 6; j++){
    //         for(int k = 0; k < 6; k++){
    //             for(int l = 0; l < 6; l++){
    //                 for(int m = 0; m < 6; m++){
    //                     for(int n = 0; n < 6; n++){
    //                         int a[6] = {i, j, k, l, m, n};
    //                         bool ok = true;
    //                         for(int idx = 0; idx < 6; idx++) if(a[a[idx]] != a[idx]) ok = false;
    //                         if(ok) for(int idx = 0; idx < 6; idx++) cout << a[idx] << " ";
    //                         if(ok) cout << endl;
    //                     }
    //                 }
    //             }
    //         }
    //     }
    // }
    // N = 7 だと, 6322通り(0 0 0 0 0 0 0 ～ 6 6 6 6 6 6 6) あるっぽい.
    // for(int i = 0; i < 7; i++){
    //    for(int j = 0; j < 7; j++){
    //         for(int k = 0; k < 7; k++){
    //             for(int l = 0; l < 7; l++){
    //                 for(int m = 0; m < 7; m++){
    //                     for(int n = 0; n < 7; n++){
    //                         for(int o = 0; o < 7; o++){
    //                             int a[7] = {i, j, k, l, m, n, o};
    //                             bool ok = true;
    //                             for(int idx = 0; idx < 7; idx++) if(a[a[idx]] != a[idx]) ok = false;
    //                             if(ok) for(int idx = 0; idx < 7; idx++) cout << a[idx] << " ";
    //                             if(ok) cout << endl;
    //                         }
    //                     }
    //                 }
    //             }
    //         }
    //     }
    // }
    // 以下のサイトに, 検索(1 3 10 41 196 1057 6322)がヒット.
    // A000248  E.g.f.: exp(x*exp(x)).
    // https://oeis.org/A000248
    // -> a(n) = Sum_{k=0..n} C(n,k)*(n-k)^k. [Paul D. Hanna, Jun 26 2009]
    // -> 上記の公式を参考に, 解答する方針とした.
    LL ans;
    ans = 0LL;
    FOR(k, 0, N + 1){
        LL c = comb(N, k), p = pow(N - k, k);
        // cout << "N=" << N << " k=" << k << " c=" << c << " p=" << p << " ";
        c *= p;
        c %= MOD;
        ans += c;
        // cout << ans << endl;
        ans %= MOD;
    }
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}
0