結果

問題 No.2975 単調増加部分積
ユーザー zawakasuzawakasu
提出日時 2024-11-29 22:58:46
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 7,471 ms / 10,000 ms
コード長 3,413 bytes
コンパイル時間 1,522 ms
コンパイル使用メモリ 129,580 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 22:59:20
合計ジャッジ時間 31,843 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 46 ms
5,248 KB
testcase_14 AC 10 ms
5,248 KB
testcase_15 AC 80 ms
5,248 KB
testcase_16 AC 3 ms
5,248 KB
testcase_17 AC 10 ms
5,248 KB
testcase_18 AC 82 ms
5,248 KB
testcase_19 AC 745 ms
5,248 KB
testcase_20 AC 7,471 ms
5,248 KB
testcase_21 AC 7,238 ms
5,248 KB
testcase_22 AC 7,137 ms
5,248 KB
testcase_23 AC 7,081 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//  頼む！！！通れ！！
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
int N, M, P;
long long add(long long L, long long R) {
    assert(0 <= L and L < P);
    assert(0 <= R and R < P);
    L += R;
    if (L >= P) L -= P;
    return L;
}
long long mult(long long L, long long R) {
    assert(0 <= L and L < P);
    assert(0 <= R and R < P);
    return (L * R) % P;
}
long long pow(long long A, long long exp) {
    long long res{1 % P};
    A %= P;
    while (exp) {
        if (exp & 1) res = mult(res, A);
        A = mult(A, A);
        exp >>= 1;
    }
    return res;
}
long long inv_mult(long long v) {
    assert(0 <= v and v < P);
    return pow(v, P - 2);
}
long long divm(long long L, long long R) {
    assert(0 <= L and L < P);
    assert(0 <= R and R < P);
    return mult(L, inv_mult(R));
}
long long solve() {
    std::vector<long long> F(N + 1, 1), invF(N + 1);
    for (int i{1} ; i <= N ; i++) F[i] = mult(F[i - 1], i);
    invF[N] = inv_mult(F[N]);
    for (int i{N} ; i >= 1 ; i--) invF[i - 1] = mult(invF[i], i);
    std::vector<long long> dp(N + 1);
    for (int i{1} ; i <= N ; i++) dp[i] = i;
    long long ans{};
    for (int i{1} ; i <= M ; i++) {
        for (int j{1} ; j <= N ; j++) {
            long long comb{mult(F[M], mult(invF[i], invF[M - i]))};
            // P(N - i, M - i)だわ。アホすぎた
            comb = mult(comb, mult(F[N - i], invF[(N - i) - (M - i)]));
            ans = add(ans, mult(dp[j], comb));
        }
        if (i == M) break;
        std::vector<long long> sum(N + 2);
        for (int j{} ; j < N + 1 ; j++) sum[j + 1] = add(sum[j], dp[j]);
        std::vector<long long> next(N + 1);
        for (int j{1} ; j <= N ; j++) next[j] = mult(j, sum[j]);
        dp = std::move(next);
    }
    ans = mult(ans, F[N - M]);
    ans = mult(ans, invF[N]);
    return ans;
}
long long brute() {
    std::vector<int> cur;
    auto dfs{[&](auto dfs, int i) -> long long {
        if (i == N or (int)cur.size() == M) {
            if (cur.empty()) return 0LL;
            long long res{1};
            for (auto c : cur) res = mult(res, c);
            // binom(M, cur.size())
            for (int i{} ; i < (int)cur.size() ; i++) {
                res = mult(res, M - i);
                res = divm(res, i + 1);
            }
            return res;
        }
        else {
            long long res{};
            res = add(res, dfs(dfs, i + 1));
            if (cur.size() < (size_t)M) {
                cur.push_back(i + 1);
                res = add(res, dfs(dfs, i + 1));
                cur.pop_back();
            }
            return res;
        }
    }};
    return dfs(dfs, 0);
}
#include <random>
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    // std::mt19937 mt{std::random_device{}()};
    std::cin >> N >> M >> P;
    std::cout << solve() << '\n';
    // while (true) {
    //     // std::cin >> N >> M >> P;
    //     N = mt() % 20 + 1;
    //     M = mt() % 20 + 1;
    //     if (N < M) std::swap(N, M);
    //     P = 23;
    //     long long a{solve()}, b{brute()};
    //     if (a != b){
    //         std::cout << N << ' ' << M << ' ' << P << std::endl;
    //         std::cout << a << ' ' << b << std::endl;
    //         std::exit(0);
    //     }
    //     // std::cout << brute() << '\n';
    //     // std::cout << solve() << '\n';
    // }
}
0