結果

問題 No.2975 単調増加部分積
コンテスト
ユーザー zawakasu
提出日時 2024-11-29 22:27:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,136 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 107,512 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 22:27:50
合計ジャッジ時間 23,892 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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]))};
            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<long long> idx(N, 1);
//     long long ans{};
//     do {
//         auto dfs{[&](auto dfs, int i) -> long long {
//             
//         }};
//     } while (std::next_permutation(idx.begin(), idx.end()));
//     return ans;
// }
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cin >> N >> M >> P;
    std::cout << solve() << '\n';
}
0