結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
#define poly basic_string<node>
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;
struct node{
	int x,y;
}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}};
node operator+(node a,node b)
{
	a.x=(a.x+b.x)%Mod,a.y=(a.y+b.y)%Mod;
	return a;
}
node operator-(node a,node b)
{
	a.x=(a.x-b.x+Mod)%Mod,a.y=(a.y-b.y+Mod)%Mod;
	return a;
}
void operator-=(node &a,node b)
{
	a.x=(a.x-b.x+Mod)%Mod,a.y=(a.y-b.y+Mod)%Mod;
}
void operator+=(node &a,node b)
{
	a.x=(a.x+b.x)%Mod,a.y=(a.y+b.y)%Mod;
}
node operator*(node a,node b)
{
	return {(a.x*b.x-3*a.y*b.y%Mod+3*Mod)%Mod,(a.x*b.y+a.y*b.x)%Mod};
}
node operator*(node a,int b)
{
	return {a.x*b%Mod,a.y*b%Mod};
}
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;
}
node ksm(node x,int y)
{
	node ret={1,0},bace=x;
	while(y)
	{
		if(y&1)ret=ret*bace;
		bace=bace*bace;
		y>>=1;
	}
	return ret;
}
node inv(node a)
{
	int val=ksm((a.x*a.x+3*a.y*a.y)%Mod,Mod-2);
	return {a.x*val%Mod,Mod-a.y*val%Mod};
}

node operator/(node a,node b)
{
	return a*inv(b);
}
namespace NTT 
{
 	node 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(node *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) 
  		{ 
   			int tmp=(op==1)?g:invg;
   			tmp=ksm(tmp,(Mod-1)/(len<<1)); 
   			for(int i=0;i<n;i+=(len<<1)) 
      		{ 
      	 		int now=1; 
       			for(int j=0;j<len;j++) 
       			{
       				if(f[i+j+len].x)f[i+j+len].x%=Mod;
					if(f[i+j+len].y)f[i+j+len].y%=Mod;
       				if(f[i+j].y||f[i+j+len].y)
       				{
        				node x=f[i+j+len]*now;
        				f[i+j+len]={f[i+j].x-x.x+Mod,f[i+j].y-x.y+Mod},f[i+j].x+=x.x,f[i+j].y+=x.y,now=now*tmp%Mod;
					}
       				else
       				{
       					int x=f[i+j+len].x*now%Mod;
       					f[i+j+len].x=f[i+j].x-x+Mod,f[i+j].x+=x,now=now*tmp%Mod;
					}
    			} 
   			} 
  		} 
  		for(int i=0;i<n;i++)
  		{
  			if(f[i].x)f[i].x%=Mod;
  			if(f[i].y)f[i].y%=Mod;
		}
  		if(op==-1) 
  		{ 
  	 		int inv=ksm(n,Mod-2); 
   			for(int i=0;i<n;i++)f[i]=f[i]*inv; 
  		} 
 	} 
 	void solve(int n,int m,node *f,node *g,node *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,0};
  		for(int i=m;i<k;i++)B[i]={0,0}; 
  		ntt(A,k,1),ntt(B,k,1);
  		for(int i=0;i<k;i++)s[i]=A[i]*B[i]; 
  		ntt(s,k,-1); 
 	} 
}
poly operator*(poly f,poly g)
{
	if(!f.size()||!g.size())return {{0,0}};
	poly h;
	if(f.size()<50||g.size()<50)
	{
		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]+=f[i]*g[j];
		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];
	return f;
}
poly calc0(poly f,node x)
{
	node now={1,0};
	for(int i=0;i<f.size();i++)f[i]=now*f[i],now=now*x;
	return f;
}
poly calc1(poly f,int k,int b)
{
	poly g;
	for(int i=b;i<f.size();i+=k)g+=f[i];
	return g;
}
poly s;
signed main()
{
	w2={Mod-1,0},w3={Mod-INV2,INV2},g=3,invg=ksm(g,Mod-2);
	scanf("%lld",&n);
	p1=p2=p3=p4=p5=1;
	s+={1,0};
	if(p1)s+={Mod-1,0};
	if(p2)s+={Mod-1,0};
	if(p3)s+={Mod-1,0};
	Q[0][0]=s,F[0]=G[0]=S[0]=P[0][0]={{1,0}},pw2[0]=pw3[0]=1;
	for(int i=0;i<=60;i++)S[i]={{1,0}};
	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]=calc1(Q[i][j]*calc0(Q[i][j],w2),2,0);
			Q[i][j+1]=calc1(Q[i][j]*calc0(Q[i][j],w3)*calc0(Q[i][j],w3*w3),3,0);
			S[i+j]=S[i+j]*Q[i][j];
		}
	for(int i=0;i<=60;i++)T[i]=S[i];
	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]=calc0(S[i],w2),W1[i]=calc0(S[i],w3)*calc0(S[i],w3*w3);
	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]/S[i+j][0];
				continue;
			}
			poly ww=P[i][j]*W0[i+j];
			if(p4)P[i+1][j]=P[i+1][j]+calc1(ww,2,tmp&1)*F[i+j+1];
			if(p5)P[i][j+1]=P[i][j+1]+calc1(P[i][j]*W1[i+j],3,tmp%3)*G[i+j+1];
			R[i+1][j]=R[i+1][j]+calc1(R[i][j]*W0[i+j]+(poly){{0,0},{1,0}}*ww,2,tmp&1)*H[i+j+1];
		}
	printf("%lld",ans.x);
	return 0;
}
0