結果

問題 No.2349 Power!! (Hard)
コンテスト
ユーザー ytqm3
提出日時 2023-06-10 21:00:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 989 ms / 7,000 ms
コード長 2,167 bytes
コンパイル時間 5,525 ms
コンパイル使用メモリ 263,400 KB
最終ジャッジ日時 2025-02-14 01:24:52
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using i64=int64_t;

template<class mint> vector<mint> MiddleProd(vector<mint> f,vector<mint> g){
  int N=f.size(),M=g.size();
  assert(N>=M);
  reverse(g.begin(),g.end());
  vector<mint> h=atcoder::convolution(f,g);
  vector<mint> res(N-M+1);
  for(int i=M-1;i<N;++i){
    res[i-(M-1)]=h[i];
  }
  return res;
}

template<class mint> vector<mint> MultiEvalGeomSeq(vector<mint> f,mint r,int M){
	if(f.size()==0){
		vector<mint> res(M);
		return res;
	}
  int N=f.size();
  auto calc=[&](mint q,int K){
    //q^Tr(i) を計算
    vector<mint> res(K,1);
    mint nw=1;
    for(int i=1;i<K;++i){
      nw*=q;
      res[i]=res[i-1]*nw;
    }
    return res;
  };
  vector<mint> A=calc(r,N+M-1),B=calc(mint(1)/r,max(N,M));
  for(int i=0;i<N;++i){ f[i]*=B[i]; }
  auto g=MiddleProd(A,f);
  for(int i=0;i<M;++i){ g[i]*=B[i]; }
  return g;
}

template<class mint> vector<mint> AllInv(vector<mint> f){
	int n=f.size();
	vector<mint> res(n+1,1);
	for(int i=0;i<n;++i){ res[i+1]=res[i]*f[i]; }
	mint t=mint(1)/res[n];
	res.pop_back();
	for(int i=n-1;i>=0;--i){
		res[i]*=t;
		t*=f[i];
	}
	return res;
}

void solve(){
	constexpr i64 P=998244353,D=(1<<13)*119,E=(P-1)/D;
	using mint=atcoder::static_modint<P>;
	i64 A,N;
	cin>>A>>N;
	i64 L=N/D,R=N%D;
	auto h=[&](int n){
		i64 m=n/E;
		vector<mint> g(m);
		mint t1=mint(A).pow(E*E),nw=1,cff=1;
		for(i64 i=0;i<m;++i){
			g[i]=nw;
			nw*=t1*cff;
			cff*=t1*t1;
		}
		auto W=MultiEvalGeomSeq(g,mint(A).pow(2*E),E);
		vector<mint> res(E);
		nw=1,cff=1;
		for(i64 i=0;i<E;++i){
			res[i]+=nw*W[i];
			nw*=A*cff;
			cff*=A*A;
		}
		nw=mint(A).pow(m*m*E*E),cff=mint(A).pow(2*m*E);
		for(i64 i=m*E;i<n;++i){
			res[i%E]+=nw;
			nw*=A*cff;
			cff*=A*A;
		}
		return res;
	};
	vector<mint> X=h(D),Y=h(R);
	mint ans=0,t2=mint(A).pow(2*D),t3=mint(A).pow(2*L*D),t4=1,t5=1;
	vector<mint> Z(E);
	for(i64 t=0;t<E;++t){
		Z[t]=-t5+1;
		if(Z[t]==0){ Z[t]=1; }
		t5*=t2;
	}
	auto H=AllInv(Z);
	for(i64 t=0;t<E;++t){
		ans+=(t5==mint(1)?L:(-t4+1)*H[t])*X[t]+t4*Y[t];
		t4*=t3;
		t5*=t2;
	}
	cout<<ans.val()<<endl;
}

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