結果

問題 No.391 CODING WAR
ユーザー tsutajtsutaj
提出日時 2018-10-12 15:02:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 1,227 bytes
コンパイル時間 506 ms
コンパイル使用メモリ 65,520 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-20 19:51:14
合計ジャッジ時間 1,375 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 22 ms
5,376 KB
testcase_10 AC 20 ms
5,376 KB
testcase_11 AC 11 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 18 ms
5,376 KB
testcase_14 AC 16 ms
5,376 KB
testcase_15 AC 17 ms
5,376 KB
testcase_16 AC 12 ms
5,376 KB
testcase_17 AC 14 ms
5,376 KB
testcase_18 AC 11 ms
5,376 KB
testcase_19 AC 10 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void init_fact()':
main.cpp:23:19: warning: iteration 100004 invokes undefined behavior [-Waggressive-loop-optimizations]
   23 |         finv[i-1] = (finv[i] * i) % MOD;
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:22:24: note: within this loop
   22 |     for(int i=MAXN-1; i>=0; i--) {
      |                       ~^~~

ソースコード

diff # 

#include <iostream>
using namespace std;

using ll = long long int;
const ll MOD = 1000000007;
const int MAXN = 100005;
ll mod_pow(ll N, ll K) {
    ll ret = 1;
    for(; K>0; K>>=1) {
        if(K & 1) (ret *= N) %= MOD;
        (N *= N) %= MOD;
    }
    return ret; // 累乗 (略)
}

ll fact[MAXN + 10], finv[MAXN + 10];
void init_fact() {
    fact[0] = 1;
    for(int i=1; i<MAXN; i++) fact[i] = (fact[i-1] * i) % MOD;

    finv[MAXN-1] = mod_pow(fact[MAXN-1], MOD-2);
    for(int i=MAXN-1; i>=0; i--) {
        finv[i-1] = (finv[i] * i) % MOD;
    }
}

ll comb(int n, int r) {
    if(r < 0 or n-r < 0) return 0;
    return fact[n] * finv[n-r] % MOD * finv[r] % MOD;
}

int main() {
    init_fact();
    ll N, K, ans = 0; cin >> N >> K;

    // 絶対に空にする箱の個数を決める
    for(int i=1; i<=K; i++) {
        int rest = K - i;
        ll val = comb(K, i) * mod_pow(rest, N) % MOD; // 対称性よりまとめて計算可能
        if(i % 2 == 1) ans = (ans + val      ) % MOD;
        else           ans = (ans - val + MOD) % MOD;
    }
    // 「どの箱にも 1 つ以上」の制約がなければ k^n 通り
    ans = (mod_pow(K, N) - ans + MOD) % MOD;
    cout << ans << endl;
    return 0;
}
0