結果

問題 No.2810 Have Another Go (Hard)
ユーザー highlighter
提出日時 2024-06-18 22:03:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 5,024 bytes
コンパイル時間 6,596 ms
コンパイル使用メモリ 338,156 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 13:32:34
合計ジャッジ時間 10,125 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint=modint998244353;
mint Bostan_Mori(vector<mint> &A,vector<mint> &C,long long N){
    int d=(int)(C.size());
    vector<mint> Q(d+1);
    Q[0]=1;
    for(int i=1;i<=d;i++){
        Q[i]=-C[i-1];
    }
    vector<mint> P=convolution(Q,A);
    P.resize(d);
    int z=(int)internal::bit_ceil((unsigned int)(2*d+1));
    mint iz=mint(z).inv();
    mint w=mint(3).pow(998244352/z);
    mint iw=w.inv();
    mint W[z/2];
    W[0]=1;
    for(int i=1;i<z/2;i++){
        W[i]=W[i-1]*iw;
    }
    auto rev=[&](int i){
        int j=0;
        int k=bit_width((unsigned int)(z/2));
        k--;
        for(;k--;){
            j= (j << 1)+(i&1);
            i >>= 1;
        }
        return j;
    };
    while(N>0){
        Q.resize(z/2);
        vector<mint> Q_minus=Q;
        for(int i=1;i<=d;i+=2){
            Q_minus[i]*=-1;
            Q[i]*=-1;
        }
        internal::butterfly(Q_minus);
        mint res=1;
        for(mint &i : Q){
            i*=res;
            res*=w;
        }
        internal::butterfly(Q);
        Q_minus.insert(Q_minus.end(),Q.begin(),Q.end());
        for(int i=0;i<z/2;i++){
            Q[i]=Q_minus[i*2+1]*Q_minus[i*2];
        }
        internal::butterfly_inv(Q);
        for(mint &i : Q){
            i*=iz*2;
        }
        Q.resize(d+1);
        P.resize(z/2);
        vector<mint> P_sub=P;
        internal::butterfly(P);
        res=1;
        for(mint &i : P_sub){
            i*=res;
            res*=w;
        }
        internal::butterfly(P_sub);
        P.insert(P.end(),P_sub.begin(),P_sub.end());
        for(int i=0;i<z;i++){
            P[i]*=Q_minus[i];
        }
        if(N%2==0){
            for(int i=0;i<z/2;i++){
                P[i]=(P[i*2]+P[i*2+1])*mint(499122177);
            }
            P.resize(z/2);
            internal::butterfly_inv(P);
            for(mint &i : P){
                i*=iz*2;
            }
            P.resize(d);
            N/=2;
            continue;
        }
        for(int i=0;i<z/2;i++){
            P[i]=(P[i*2]-P[i*2+1])*mint(499122177);
            P[i]*=W[rev(i)];
        }
        P.resize(z/2);
        internal::butterfly_inv(P);
        for(mint &i : P){
            i*=iz*2;
        }
        P.resize(d);
        N/=2;
        continue;
    }
    return P[0]/Q[0];
}
template<typename T>
struct matrix{
    int H,W;
    vector<vector<T>> table;
    matrix(int h,int w) : H(h),W(w){
        table.resize(h,vector<T>(w));
    }
    int size(){
        return H;
    }
    matrix pow(long long N){
        assert(H==W);
        assert(0<=N);
        matrix x=*this;
        matrix r(H,H);
        for(int i=0;i<H;i++){
            r[i][i]=1;
        }
        while(N){
            if(N&1)r*=x;
            x*=x;
            N>>=1;
        }
        return r;
    }
    vector<T>& operator[](int index){
        assert(index<H);
        return table[index];
    }
    matrix& operator+=(const matrix &other){
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if((int)(other.table.size())<=i){
                    continue;
                }
                if((int)(other.table[i].size())<=j){
                    continue;
                }
                (*this)[i][j]+=other.table[i][j];
            }
        }
        return *this;
    }
    matrix operator*=(const matrix &other){
        int h=other.H;
        int w=other.W;
        assert(h==W);
        //結果はH*w行列になる
        matrix result(H,w);
        for(int i=0;i<H;i++){
            for(int k=0;k<W;k++){
                for(int j=0;j<w;j++){
                    result.table[i][j]+=table[i][k]*other.table[k][j];
                }
            }
        }
        *this=result;
        return *this;
    }
};
int main(){
    int N,k;
    long long M;
    scanf("%d%lld%d",&N,&M,&k);
    //1,1,2,4,8,16で始まり，前6項を足す線型漸化式に使うvectorを用意しておく
    vector<mint> A(6);
    A[0]=1;
    A[1]=1;
    A[2]=2;
    A[3]=4;
    A[4]=8;
    A[5]=16;
    vector<mint> c(6,mint(1));
    for(;k--;){
        int C;
        scanf("%d",&C);
        vector<vector<mint>> P(6,vector<mint>(6));
        //P[i][j]:X=iからスタートして，X=N+j(ピッタリ)で終わるサイコロの振り方であって，常にX \not \equiv C (mod N)である場合
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(i==C){
                    P[i][j]=0;
                    continue;
                }
                if(j==C){
                    P[i][j]=0;
                    continue;
                }
                if(i<C && j<C){
                    P[i][j]=Bostan_Mori(A,c,C-i);
                    P[i][j]*=Bostan_Mori(A,c,N+j-C);
                    P[i][j]=Bostan_Mori(A,c,N+j-i)-P[i][j];
                    continue;
                }
                if(C<j && C<i){
                    P[i][j]=Bostan_Mori(A,c,N+C-i);
                    P[i][j]*=Bostan_Mori(A,c,j-C);
                    P[i][j]=Bostan_Mori(A,c,N+j-i)-P[i][j];
                    continue;
                }
                if(i<C && C<j){
                    mint res1=Bostan_Mori(A,c,C-i);
                    mint res2=Bostan_Mori(A,c,N);
                    mint res3=Bostan_Mori(A,c,j-C);
                    mint res4=Bostan_Mori(A,c,N+C-i);
                    mint res5=Bostan_Mori(A,c,N+j-C);
                    mint res6=Bostan_Mori(A,c,N+j-i);
                    P[i][j]=res6-res1*res5-res4*res3+res1*res2*res3;
                    continue;
                }
                P[i][j]=Bostan_Mori(A,c,N+j-i);
            }
        }
        matrix<mint> Q(6,6);
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                Q[i][j]=P[j][i];
            }
        }
        Q=Q.pow(M-2);//to do:M=1の場合に場合分けして書く
        matrix<mint> R(6,1);
        for(int i=0;i<6;i++){
            R[i][0]=P[0][i];
        }
        Q*=R;
        vector<mint> S(6);
        for(int i=0;i<6;i++){
            if(Q[i][0]==0){
                continue;
            }
            for(int j=0;j<6;j++){
                //iからN+jに動く
                //N~N+jの間のCについては無視
                if(i<C){
                    mint res=Bostan_Mori(A,c,C-i)*Bostan_Mori(A,c,N+j-C);
                    res=Bostan_Mori(A,c,N+j-i)-res;
                    S[j]+=res*Q[i][0];
                    continue;
                }
                assert(i!=C);
                mint res=Bostan_Mori(A,c,N+j-i);
                S[j]+=res*Q[i][0];
            }
        }
        mint ans=0;
        for(int i=5;i>=0;i--){
            for(int j=i-1;j>=0;j--){
                S[i]-=S[j];
            }
            ans+=S[i];
        }
        printf("%d\n",ans.val());
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0