結果

問題 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;

}
0