結果

問題 No.1035 Color Box
ユーザー Strorkis
提出日時 2020-04-24 23:00:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,161 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 70,244 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 03:39:54
合計ジャッジ時間 1,827 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

const long long MOD = 1000000007;

int main() {
    int N, M;
    std::cin >> N >> M;

    auto pow = [](long long a, int n) {
        long long res = 1;
        for (; n; n >>= 1) {
            if (n & 1)
                res = res * a % MOD;
            a = a * a % MOD;
        }
        return res;
    };

    std::vector<long long> table(N + 1), inv_table(N + 1);
    table[0] = 1;
    for (int i = 1; i <= N; i++)
        table[i] = table[i - 1] * i % MOD;
    inv_table[N] = pow(table[N], MOD - 2);
    for (int i = N; i > 0; i--)
        inv_table[i - 1] = inv_table[i] * i % MOD;

    auto comb = [&table, &inv_table](int n, int r) {
        if (n < r)
            return 0LL;
        long long tmp = inv_table[n - r] * inv_table[r] % MOD;
        return table[n] * tmp % MOD;
    };

    long long ans = pow(M, N);
    for (int i = M - 1; i > 0; i--) {
        if ((M + i) % 2) {
            ans -= comb(M, i) * pow(i, N) % MOD;
            ans += ans < 0 ? MOD : 0;
        }
        else {
            ans += comb(M, i) * pow(i, N) % MOD;
            ans %= MOD;
        }
    }
    std::cout << ans << "\n";
}
0