結果

問題 No.2996 Floor Sum
ユーザー 👑 testestest
提出日時 2024-12-15 12:02:47
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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,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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0