結果

問題 No.2996 Floor Sum
ユーザー 👑 testestesttestestest
提出日時 2024-12-15 12:02:47
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,841 ms / 5,000 ms
コード長 2,253 bytes
コンパイル時間 3,525 ms
コンパイル使用メモリ 270,084 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 18:06:32
合計ジャッジ時間 10,099 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 237 ms
6,820 KB
testcase_02 AC 3 ms
6,816 KB
testcase_03 AC 1,717 ms
6,820 KB
testcase_04 AC 101 ms
6,820 KB
testcase_05 AC 279 ms
6,820 KB
testcase_06 AC 1,841 ms
6,816 KB
testcase_07 AC 8 ms
6,820 KB
testcase_08 AC 39 ms
6,820 KB
testcase_09 AC 6 ms
6,816 KB
testcase_10 AC 7 ms
6,816 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 9 ms
6,820 KB
testcase_13 AC 1,756 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
using ll=long long;
#define rep(i,l,r)for(int i=(l);i<(r);i++)

mint eval(vector<mint>&f,mint x){
	mint ans=0;
	for(int i=(int)f.size()-1;i>=0;i--)ans=ans*x+f[i];
	return ans;
}

vector<mint> newton_interpolation(vector<mint>&x,vector<mint>&y){
	vector<mint>ret;
	vector<mint>f({1});
	rep(i,0,x.size()){
		mint e=eval(f,x[i]);
		mint c=eval(ret,x[i]);
		mint coef = (y[i]-c)/e;
		ret.push_back(0);
		rep(j,0,f.size())ret[j]+=coef*f[j];
		for(int j=(int)f.size()-1;j>0;j--)f[j]=f[j]*-x[i]+f[j-1];
		f[0]*=-x[i];
		f.push_back(1);
	}
	while(ret.back()==0)ret.pop_back();
	return ret;
}


vector<vector<mint>>S;
vector<mint>fact(25),invfact(25);
void precalc(){
	rep(i,0,25){
		vector<mint>x({0});
		vector<mint>y({0});
		rep(k,1,30){
			x.push_back(k);
			y.push_back(y.back()+mint(k-1).pow(i));
		}
		S.push_back(newton_interpolation(x,y));
	}
	
	fact[0]=invfact[0]=1;
	rep(i,1,25){
		fact[i]=fact[i-1]*i;
		invfact[i]=invfact[i-1]/i;
	}
}

mint choose(int n,int p,int q){
	return fact[n]*invfact[p]*invfact[q]*invfact[n-p-q];
}

void solve(){
	int p,q,M,A,B;
	ll N;
	cin >> p >> q >> N >> M >> A >> B;
	N++;
	
	vector<vector<unordered_map<int,mint>>>memo(21,vector<unordered_map<int,mint>>(21));
	auto solve_main=[&](int p,int q,ll N, int M,int A,ll B,auto sub)->mint{
		int a1=A/M,a2=A%M;
		if(a2<0)a2+=M,a1--;
		ll b1=B/M,b2=B%M;
		if(b2<0)b2+=M,b1--;
		mint ans=0;
		rep(r,0,q+1)rep(s,0,q-r+1){
			mint coef = choose(q,r,s) * mint(a1).pow(s) * mint(b1).pow(q-r-s);
			if(coef!=0)ans+=coef*sub(p+s,r,N,M,a2,b2,sub);
		}
		return ans;
	};
	
	auto solve_sub=[&](int p,int q,ll N,int M,int A,int B,auto self)->mint{
		if(memo[p][q].find(M)!=memo[p][q].end())return memo[p][q][M];
		if(N==0)return 0;
		if(q==0)return eval(S[p],N);
		ll K=(A*(N-1)+B)/M, Kr=(A*(N-1)+B)%M;
		if(Kr<0)K--;
		if(K==0)return 0;
		mint ans=mint(K).pow(q)*eval(S[p],N);
		rep(i,0,q)rep(j,0,p+2){
			mint coef=choose(q,i,0)*S[p][j];
			if(coef!=0){
				ans-=coef*solve_main(i,j,K,A,M,(ll)M-B+A-1,self);
			}
		}
		return memo[p][q][M]=ans;
	};
	
	cout << solve_main(p,q,N,M,A,B,solve_sub).val() << endl;
}

int main(){
	precalc();
	int t;
	cin >> t;
	while(t--)solve();
}
0