結果

問題 No.3399 One Two Three Two Three
コンテスト
ユーザー lishujia090623
提出日時 2026-01-10 23:54:26
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 4,068 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,052 ms
コンパイル使用メモリ 243,012 KB
実行使用メモリ 66,704 KB
最終ジャッジ日時 2026-01-10 23:55:23
合計ジャッジ時間 54,992 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35 TLE * 2 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
#define poly basic_string<int>
using namespace std;
const int N=65,M=1e5+5,Mod=998244353,INV2=499122177;
int n,p1,p2,p3,p4,p5,pw2[N],pw3[N],g,invg,w2,w3,ans,a[M],b[M],c[M];
poly P[N][N],Q[N][N],R[N][N],S[N],T[N],F[N],G[N],H[N],W0[N],W1[N],now={{1,0}};
int ksm(int x,int y)
{
	int ret=1,bace=x;
	while(y)
	{
		if(y&1)ret=ret*bace%Mod;
		bace=bace*bace%Mod;
		y>>=1;
	}
	return ret;
}
namespace NTT 
{ 
 	long long A[M],B[M]; 
	int tr[M]; 
	int init(int n) 
 	{ 
  		int ret=1; 
  		while(ret<n)ret<<=1; 
  		for(int i=0;i<ret;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(ret>>1):0); 
  		return ret; 
 	} 
 	void ntt(long long *f,int n,int op) 
 	{ 
  		for(int i=0;i<n;i++)if(i<tr[i])swap(f[i],f[tr[i]]); 
  		for(int len=1;len<n;len<<=1) 
  		{ 
   			long long tmp=(op==1)?g:invg; 
   			tmp=ksm(tmp,(Mod-1)/(len<<1)); 
   			for(int i=0;i<n;i+=(len<<1)) 
      		{ 
      	 		long long now=1; 
       			for(int j=0;j<len;j++) 
       			{ 
        			long long x=now*(f[i+j+len]%=Mod)%Mod; 
        			f[i+j+len]=f[i+j]-x+Mod,f[i+j]+=x,now=now*tmp%Mod; 
    			} 
   			} 
  		} 
  		for(int i=0;i<n;i++)f[i]%=Mod;
  		if(op==-1) 
  		{ 
  	 		long long inv=ksm(n,Mod-2); 
   			for(int i=0;i<n;i++)f[i]=inv*f[i]%Mod; 
  		} 
 	}
 	void solve(int n,int m,long long *f,long long *g,long long *s) 
 	{ 
  		int k=init(n+m); 
  		for(int i=0;i<n;i++)A[i]=f[i]; 
  		for(int i=0;i<m;i++)B[i]=g[i]; 
  		for(int i=n;i<k;i++)A[i]=0; 
  		for(int i=m;i<k;i++)B[i]=0; 
  		ntt(A,k,1),ntt(B,k,1); 
  		for(int i=0;i<k;i++)s[i]=A[i]*B[i]%Mod; 
  		ntt(s,k,-1); 
 	} 
}
poly operator*(poly f,poly g)
{
	if(!f.size()||!g.size())return {0};
	poly h;
	if(f.size()<30&&g.size()<30)
	{
		h.resize(f.size()+g.size()-1);
		for(int i=0;i<f.size();i++)for(int j=0;j<g.size();j++)h[i+j]=(h[i+j]+f[i]*g[j])%Mod;
		return h;
	}
	for(int i=0;i<f.size();i++)a[i]=f[i];
	for(int i=0;i<g.size();i++)b[i]=g[i];
	NTT::solve(f.size(),g.size(),a,b,c);
	for(int i=0;i<f.size()+g.size()-1;i++)h+=c[i];
	return h;
}
poly operator+(poly f,poly g)
{
	if(f.size()<g.size())swap(f,g);
	for(int i=0;i<g.size();i++)f[i]+=g[i],f[i]%=Mod;
	return f;
}
poly operator-(poly f,poly g)
{
	if(f.size()<g.size())f.resize(g.size());
	for(int i=0;i<g.size();i++)f[i]=(f[i]-g[i]+Mod)%Mod;
	return f;
}
poly calc(poly f,int k,int b)
{
	poly g;
	for(int i=b;i<f.size();i+=k)g+=f[i];
	return g;
}
poly calc1(poly f,int k,int b)
{
	poly g;
	g.resize(f.size());
	for(int i=0;i<f.size();i++)if(i%k==b)g[(i-b)/k*k]=f[i];
	return g;
}
poly calc2(poly F)
{
	poly A0=calc(F,2,0),A1=calc(F,2,1);
	return A0*A0-(poly){0,1}*A1*A1;
}
poly calc3(poly F)
{
	poly A0=calc(F,3,0),A1=calc(F,3,1),A2=calc(F,3,2);
	return A0*A0*A0+(poly){0,1}*A1*A1*A1+(poly){0,0,1}*A2*A2*A2-(poly){0,3}*A0*A1*A2;
}
poly s;
signed main()
{
	g=3,invg=ksm(g,Mod-2);
	scanf("%lld",&n);
	p1=p2=p3=p4=p5=1;
	s+=1;
	if(p1)s+=Mod-1;
	if(p2)s+=Mod-1;
	if(p3)s+=Mod-1;
	Q[0][0]=s,F[0]=G[0]=S[0]=P[0][0]={1},pw2[0]=pw3[0]=1;
	for(int i=0;i<=60;i++)S[i]={1};
	for(int i=1;i<=60;i++)pw2[i]=2*pw2[i-1],pw3[i]=3*pw3[i-1];
	for(int i=0;i<=60;i++)
		for(int j=0;j<=60;j++)
		{
			Q[i+1][j]=calc2(Q[i][j]);
			Q[i][j+1]=calc3(Q[i][j]);
			S[i+j]=S[i+j]*Q[i][j];
		}
	H[0]=s;
	for(int i=1;i<=60;i++)S[i]=S[i]*S[i-1],F[i]=F[i-1]*Q[0][i],G[i]=G[i-1]*Q[i][0],H[i]=H[i-1]*Q[0][i];
	for(int i=0;i<=60;i++)
	{
		W0[i]=S[i];
		for(int j=1;j<W0[i].size();j+=2)W0[i][j]=Mod-W0[i][j];
		poly A=calc1(S[i],3,0),B=calc1(S[i],3,1),C=calc1(S[i],3,2);
		W1[i]=A*A-(poly){0,1}*A*B+(poly){0,0,1}*(B*B-A*C)-(poly){0,0,0,1}*B*C+(poly){0,0,0,0,1}*C*C;
		while(!W1[i].back())W1[i].pop_back();
	}
	for(int i=0;i<=60;i++)
		for(int j=0;j<=38&&i+j<=60;j++)
		{
			int tmp=n/pw2[i]/pw3[j];
			if(!tmp)
			{
				if(R[i][j].size())ans+=R[i][j][0]*ksm(S[i+j][0],Mod-2),ans%=Mod;
				continue;
			}
			poly ww=P[i][j]*W0[i+j];
			if(p4)P[i+1][j]=P[i+1][j]+calc(ww,2,tmp&1)*F[i+j+1];
			if(p5)P[i][j+1]=P[i][j+1]+calc(P[i][j]*W1[i+j],3,tmp%3)*G[i+j+1];
			R[i+1][j]=R[i+1][j]+calc(R[i][j]*W0[i+j]+(poly){0,1}*ww,2,tmp&1)*H[i+j+1];
		}
	printf("%lld",ans);
	return 0;
}
0