結果

問題 No.2413 Multiple of 99
ユーザー i_am_noobi_am_noob
提出日時 2023-08-11 22:50:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 682 ms / 8,000 ms
コード長 2,864 bytes
コンパイル時間 2,403 ms
コンパイル使用メモリ 210,156 KB
実行使用メモリ 38,876 KB
最終ジャッジ日時 2024-11-18 17:57:43
合計ジャッジ時間 11,199 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

const int mod=998244353,G=3,N=1<<20;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return ((ll)x)*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; x=mul(x,x),y>>=1) if(y&1) res=mul(res,x); return res;}

int fac[N],inv[N],ifac[N];
inline int C(int n, int m){if(m<0||m>n) return 0; return mul(fac[n],mul(ifac[m],ifac[n-m]));}
void init_comb(){
    fac[0]=inv[1]=ifac[0]=1;
    for(int i=1; i<N; ++i) fac[i]=mul(fac[i-1],i);
    for(int i=2; i<N; ++i) inv[i]=mul(inv[mod%i],mod-mod/i);
    for(int i=1; i<N; ++i) ifac[i]=mul(ifac[i-1],inv[i]);
}

struct NTT{
    int w[N];
    NTT(){
        int dw=Pow(G,(mod-1)/N);
        w[0]=1;
        for(int i=1; i<N; ++i) w[i]=mul(w[i-1],dw);
    }
    void bitrev(vector<int>& a, int n){
        int i=0;
        for(int j=1; j<n-1; ++j){
            for(int k=n>>1; (i^=k)<k; k>>=1);
            if(j<i) swap(a[i],a[j]);
        }
    }
    void operator()(vector<int>& a, int n, bool inv=0){
        bitrev(a,n);
        for(int L=2; L<=n; L<<=1){
            int dx=N/L,dl=L>>1;
            for(int i=0; i<n; i+=L){
                for(int j=i,x=0; j<i+dl; ++j,x+=dx){
                    int tmp=mul(a[j+dl],w[x]);
                    a[j+dl]=sub(a[j],tmp);
                    a[j]=add(a[j],tmp);
                }
            }
        }
        if(inv){
            reverse(a.begin()+1,a.end());
            int invn=Pow(n);
            for(int i=0; i<n; ++i) a[i]=mul(a[i],invn);
        }
    }
}ntt;
vector<int> Mul(vector<int> a, vector<int> b, int M=N){
    if(a.empty()&&b.empty()) return {};
    int m=a.size()+b.size()-1,n=1;
    while(n<m) n<<=1;
    a.resize(n),b.resize(n);
    ntt(a,n),ntt(b,n);
    for(int i=0; i<n; ++i) a[i]=mul(a[i],b[i]);
    ntt(a,n,1);
    a.resize(min(m,M));
    return a;
}

vector<int> get(int n){
    vector<int> a(n*9+1),b(n*9+1);
    for(int i=0; i<=n*9; ++i) b[i]=C(i+n-1,n-1);
    for(int i=0; i*10<=n*9; ++i){
        if(i%2==0) a[i*10]=C(n,i);
        else a[i*10]=sub(0,C(n,i));
    }
    return Mul(a,b,n*9+1);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    init_comb();
    int n,k; cin >> n >> k;
    auto vec1=get(n/2),vec2=get((n+1)/2);
    int res=0;
    for(int r=0; r<11; ++r){
        //cout << r << endl;
        vector<int> vec3,vec4;
        for(int i=r; i<sz(vec1); i+=11) vec3.pb(vec1[i]);
        for(int i=r; i<sz(vec2); i+=11) vec4.pb(vec2[i]);
        auto de=Mul(vec3,vec4);
        for(int i=0; i<sz(de); ++i) if((i*11+2*r)%9==0) res=add(res,mul(de[i],Pow(i*11+2*r,k)));//,cout << i << ' ' << i*11+2*r << ' ' << de[i] << "\n";
    }
    cout << res << "\n";
}
0