結果

問題 No.2996 Floor Sum
コンテスト
ユーザー 👑 testestest
提出日時 2024-12-20 16:37:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,355 ms / 5,000 ms
コード長 2,159 bytes
コンパイル時間 3,190 ms
コンパイル使用メモリ 273,020 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 18:07:08
合計ジャッジ時間 6,768 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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;
	ll N,B;
	cin >> p >> q >> N >> M >> A >> B;
	N++;
	mint ans=0;

	unordered_map<int,unordered_map<int,mint>>memo_main;
	memo_main[p][q]=1;
	while(N>0 && memo_main.size()>0){
		unordered_map<int,unordered_map<int,mint>>memo_sub;
		int a1=A/M;A%=M;
		if(A<0)A+=M,a1--;
		ll b1=B/M;B%=M;
		if(B<0)B+=M,b1--;
		for(auto[p,qv]:memo_main)for(auto[q,v]:qv){
			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)memo_sub[p+s][r]+=coef*v;
			}
		}
		
		memo_main.clear();
		ll K=(A*(N-1)+B)/M, Kr=(A*(N-1)+B)%M;
		if(Kr<0)K--;
		for(auto[p,qv]:memo_sub)for(auto[q,v]:qv){
			if(q==0){
				ans+=eval(S[p],N)*v;
			}else if(K!=0){
				ans+=mint(K).pow(q)*eval(S[p],N)*v;
				rep(i,0,q)rep(j,0,p+2){
					mint coef=choose(q,i,0)*S[p][j];
					if(coef!=0){
						memo_main[i][j]-=coef*v;
					}
				}
			}
		}
		B=M-B+A-1;
		N=K;
		swap(A,M);
	}
	
	cout << ans.val() << endl;
}

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