結果

問題 No.2975 単調増加部分積
ユーザー shobonvip
提出日時 2024-11-29 23:13:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 10,000 ms
コード長 3,824 bytes
コンパイル時間 5,316 ms
コンパイル使用メモリ 271,780 KB
最終ジャッジ日時 2025-02-26 09:29:17
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/**
    author:  shobonvip
    created: 2024.11.29 22:55:48
**/
#include<bits/stdc++.h>
using namespace std;
//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef dynamic_modint<0> mint;
//*/
/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/
typedef long long ll;
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()
template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T> T max(vector<T> &a){
    assert(!a.empty());
    T ret = a[0];
    for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
    return ret;
}
template <typename T> T min(vector<T> &a){
    assert(!a.empty());
    T ret = a[0];
    for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
    return ret;
}
template <typename T> T sum(vector<T> &a){
    T ret = 0;
    for (int i=0; i<(int)a.size(); i++) ret += a[i];
    return ret;
}
mint Garner(vector<long long> m,vector<long long> r){
    int n = m.size();
    vector<long long> t(n);
    for(int i=0; i<n; i++){
        long long cur = 0LL;
        long long cm = 1LL;
        for(int j=0; j<i; j++){
            cur += t[j] * cm;
            cur %= m[i];
            cm *= m[j];
            cm %= m[i];
        }
        cur = r[i] - cur;
        cur %= m[i];
        if(cur<0)cur += m[i];
        if(i==1)cur *= 416537774;
        if(i==2)cur *= 429847628;
        
        //cur *= inv_mod(cm,m[i]);
        
        cur %= m[i];
        t[i] = cur;
    }
    
    mint ret = 0;
    mint cm = 1;
    for(int i=0; i<n; i++){
        ret += cm * t[i];
        cm *= m[i];
    }
    return ret;
    
}
template <class T>
vector<T> convolution_mint(vector<T> a,vector<T> b){
    
    static constexpr unsigned long long M0 = 998244353;
    static constexpr unsigned long long M1 = 754974721;
    static constexpr unsigned long long M2 = 469762049;
    
    vector<long long> aa(a.size()),bb(b.size());
    for(int i=0; i<a.size(); i++)aa[i] = a[i].val();
    for(int i=0; i<b.size(); i++)bb[i] = b[i].val();
    
    auto c0 = convolution<M0>(aa,bb);
    auto c1 = convolution<M1>(aa,bb);
    auto c2 = convolution<M2>(aa,bb);
    
    vector<mint> ret(c0.size());
    vector<long long> m = {M0,M1,M2};
    for(int i=0; i<c0.size(); i++){
        vector<long long> r = {c0[i],c1[i],c2[i]};
        vector<long long> t(3);
        for(int j=0; j<3; j++){
            long long cur = 0LL;
            long long cm = 1LL;
            for(int k=0; k<j; k++){
                cur += t[k] * cm;
                cur %= m[j];
                cm *= m[k];
                cm %= m[j];
            }
            cur = r[j] - cur;
            cur %= m[j];
            if(cur<0)cur += m[j];
            if(j==1)cur *= 416537774;
            if(j==2)cur *= 429847628;
            cur %= m[j];
            t[j] = cur;
        }
        
        mint cm = 1;
        for(int j=0; j<3; j++){
            ret[i] += cm * t[j];
            cm *= m[j];
        }
    }
    
    return ret;
}
// Product of Polynomial Sequences
// O(N log^2 N) time, O(N) space
template<typename T>
std::vector<T> poly_prod(std::vector<std::vector<T>> f) {
    if ((int)f.size() == 0) return {1};
    std::deque<std::vector<T>> p;
    for (int i=0; i<(int)f.size(); i++){
        p.push_back(f[i]);
    }
    while((int)p.size() > 1) {
        std::vector<T> p1 = p.back(); p.pop_back();
        std::vector<T> p2 = p.back(); p.pop_back();
        p.push_front(convolution_mint(p1, p2));
    }
    return p.back();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, m, p; cin >> n >> m >> p;
    mint::set_mod(p);
    vector<mint> fact(n+1), factinv(n+1);
    fact[0] = 1;
    rep(i,1,n+1) fact[i] = fact[i-1] * i;
    factinv[n] = fact[n].inv();
    rrep(i,0,n) factinv[i] = factinv[i+1] * (i + 1);
    vector<vector<mint>> ft;
    rep(i,0,n) ft.push_back({1, i+1});
    vector<mint> f = poly_prod(ft);
    mint ans = 0;
    rep(k,1,m+1){
        ans += fact[m]*factinv[k]*factinv[m-k]*factinv[k]*f[k]*fact[k]*fact[n-k]*factinv[n];
        //cout << ans.val() << endl;
    }
    cout << ans.val() << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0