結果

問題 No.3080 Colonies on Line
ユーザー kaichou243
提出日時 2025-02-16 17:48:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,424 ms / 6,500 ms
コード長 6,907 bytes
コンパイル時間 4,889 ms
コンパイル使用メモリ 262,704 KB
実行使用メモリ 10,104 KB
最終ジャッジ日時 2025-03-27 13:07:08
合計ジャッジ時間 23,368 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<atcoder/all>
#include<bits/stdc++.h>
using namespace std;
using namespace atcoder;
using ll=long long;
using i64=int64_t;
static constexpr int mod1=167772161;
static constexpr int mod2=469762049;
static constexpr int mod3=754974721;
static constexpr int r01 = 104391568;
static constexpr int r02 = 323560596;
static constexpr int r12 = 399692502;
static constexpr int r02r12 = 190329765;
static constexpr i64 w1 = mod1;
static constexpr i64 w2 = i64(mod1) * mod2;
template<typename mint>
vector<mint> arbitrary_mod_convolution(vector<mint> a,vector<mint> b){
    ll MOD=mint::mod();
    int n=a.size(),m=b.size();
    vector<ll> x(n),y(m);
    for(int i=0;i<n;i++){
        ll tmp=a[i].val();
        x[i]=tmp;
    }
    for(int i=0;i<m;i++){
        ll tmp=b[i].val();
        y[i]=tmp;
    }
    auto z1=convolution<mod1>(x,y);
    auto z2=convolution<mod2>(x,y);
    auto z3=convolution<mod3>(x,y);
    static const int W1 = w1%MOD, W2 = w2%MOD;
    vector<mint> res(n+m-1);
    for(int i=0;i<n+m-1;i++){
        int n1 = z2[i], n2 = z3[i], a = z1[i];
        int b = i64(n1 + mod2 - a) * r01 % mod2;
        int c = (i64(n2 + mod3 - a) * r02r12 + i64(mod3- b) * r12) % mod3;
        res[i] = mint(i64(a) + i64(b) * W1 + i64(c) * W2);
    }
    return res;
}
//任意modtatamikomi
template<typename T> struct FormalPowerSeries : vector<T>{
    using vector<T>::vector;
    template<class...Args>
    FormalPowerSeries(Args...args) : vector<T>(args...){}
    FormalPowerSeries operator*(const FormalPowerSeries &b) const;
    FormalPowerSeries operator+(const FormalPowerSeries &b) const;
    FormalPowerSeries operator*(T c) const;
    FormalPowerSeries operator+(T c) const;
    FormalPowerSeries operator-(const FormalPowerSeries &b) const;
    FormalPowerSeries operator<<(int x) const;
    FormalPowerSeries operator>>(int x) const;
};
template<typename T>
FormalPowerSeries<T> pre(const FormalPowerSeries<T> &f,int deg){
    return FormalPowerSeries<T>(begin(f),begin(f)+min((int)f.size(),deg));
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator*(const FormalPowerSeries<T> &b) const {
    return convolution((*this),b);
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator*(T c) const {
    FormalPowerSeries<T> res(this->size());
    for(int i=0;i<this->size();i++) res[i]=(*this)[i]*c;
    return res;
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator+(const FormalPowerSeries<T> &b) const {
    FormalPowerSeries<T> res=(*this);
    if(b.size()>this->size()) res.resize(b.size());
    for(int i=0;i<b.size();i++) res[i]+=b[i];
    return res;
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator+(T c) const {
    FormalPowerSeries<T> res=(*this);
    res[0]+=c;
    return res;
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator-(const FormalPowerSeries<T> &b) const {
    FormalPowerSeries<T> res=(*this);
    if(b.size()>this->size()) res.resize(b.size());
    for(int i=0;i<b.size();i++) res[i]-=b[i];
    return res;
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator<<(int x) const {
    FormalPowerSeries<T> res(x,0);
    res.insert(res.end(),begin(*this),end(*this));
    return res;
}
template<typename T>
FormalPowerSeries<T> FormalPowerSeries<T>::operator>>(int x) const {
    FormalPowerSeries<T> res;
    res.insert(res.end(),begin(*this)+x,end(*this));
    return res;
}
template<typename T>
FormalPowerSeries<T>  integral(const FormalPowerSeries<T> &f){
    int n=(int)f.size();
    FormalPowerSeries<T> res(n+1,0);
    for(int i=0;i<n;i++) res[i+1]=f[i]/(i+1);
    return res;
}
template<typename T>
FormalPowerSeries<T> diff(const FormalPowerSeries<T> &f){
    int n=(int)f.size();
    FormalPowerSeries<T> res(n-1,0);
    for(int i=1;i<n;i++) res[i-1]=f[i]*i;
    return res;
}
template<typename T>
FormalPowerSeries<T> inv(const FormalPowerSeries<T> &f,int deg=-1){
    assert(f[0]!=0);
    if(deg<0) deg=(int)f.size();
    FormalPowerSeries<T> res({T(1)/f[0]});
    for(int i=1;i<deg;i<<=1){
        res=pre(res+res-res*res*pre(f,i<<1),i<<1);
    }
    return pre(res,deg);
}
template<typename T>
FormalPowerSeries<T> log(const FormalPowerSeries<T> &f,int deg=-1){
    assert(f[0]==1);
    if(deg<0) deg=(int)f.size();
    FormalPowerSeries<T> res=integral(pre(diff(f)*inv(f,deg),deg-1));
    return res;
}
template<typename T>
FormalPowerSeries<T> exp(const FormalPowerSeries<T> &f,int deg=-1){
    assert(f[0]==0);
    if(deg<0) deg=(int)f.size();
    FormalPowerSeries<T> res(1,1);
    for(int i=1;i<deg;i<<=1){
        res=res*pre(pre(f,i<<1)-log(res,i<<1)+T(1),i<<1);
        res.resize(i<<1);
    }
    return pre(res,deg);
}
template<typename T>
FormalPowerSeries<T> pow(const FormalPowerSeries<T> &f,ll e,int deg=-1){
    if(deg<0) deg=(int)f.size();
    ll i=0;
    if(e==0){
        FormalPowerSeries<T> res(deg);
        res[0]=1;
        return res;
    }
    while(i<(int)f.size()&&f[i]==0&&i*e<deg) i++;
    if(i==(int)f.size()) return FormalPowerSeries<T>(deg,0);
    if(i*e>=deg) return FormalPowerSeries<T>(deg,0);
    T k=f[i];
    FormalPowerSeries<T> res=exp(log((f>>i)*k.inv())*T(e),deg)*k.pow(e)<<(e*i);
    return pre(res,deg);
}
//任意mod形式的冪級数
template<typename mint> struct BinomCoeff{
    vector<mint> fac,rfac;
    BinomCoeff(int siz) : fac(siz), rfac(siz){
        fac[0]=1;
        for(int i=1;i<siz;i++) fac[i]=fac[i-1]*i;
        rfac[siz-1]=fac[siz-1].inv();
        for(int i=siz-1;i>0;i--) rfac[i-1]=rfac[i]*i;
    }
    mint fact(int n){
        return fac[n];
    }
    mint rfact(int n){
        return rfac[n];
    }
    mint C(int n,int k){
        if(n<k||n<0||k<0) return 0;
        return fac[n]*rfac[n-k]*rfac[k];
    }
};
//十分に大きい素数mod二項係数
template<typename mint>
mint Bostan_Mori(ll n,FormalPowerSeries<mint> P,FormalPowerSeries<mint> Q){
    while(n){
        auto C=Q;
        for(int i=1;i<C.size();i+=2) C[i]*=-1;
        P=P*C;
        Q=Q*C;
        FormalPowerSeries<mint> H;
        for(int i=(n&1ll);i<P.size();i+=2) H.push_back(P[i]);
        P=H;
        FormalPowerSeries<mint> L;
        for(int i=0;i<Q.size();i+=2) L.push_back(Q[i]);
        Q=L;
        n>>=1;
    }
    return P[0]/Q[0];
}
using mint=modint998244353;
using fps=FormalPowerSeries<mint>;
int main(){
    ll n,k;
    cin >> n >> k;
    //めんどすぎて助けてくれ〜
    //f=x^2(1-x^k)/(1-2x+x^(k+1))とする
    //1/(1-x)+1/(1-x)^2f*1/(1-fx^k/(1-x))なので
    //(1 - 3 x + 3 x^2 + x^(1 + k) - 3 x^(2 + k) + x^(2 + 2 k))/((1-x) (1 - 3 x + 2 x^2 + x^(1 + k) - 2 x^(2 + k) + x^(2 + 2 k)))
    //大変です....
    fps f(k*2+5),g(k*2+5);
    f[0]+=1,f[1]+=-3,f[2]+=3,f[k+1]+=1,f[k+2]+=-3,f[k*2+2]+=1;
    g[0]+=1,g[1]+=-3,g[2]+=2,g[k+1]+=1,g[k+2]+=-2,g[k*2+2]+=1;
    g=g*fps{1,-1};
    mint ans=Bostan_Mori(n,f,g);
    cout << ans.val() << endl;
}
0