結果

問題 No.391 CODING WAR
コンテスト
ユーザー tsutaj
提出日時 2018-10-12 15:02:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 1,227 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 65,288 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 17:46:26
合計ジャッジ時間 1,440 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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