细胞

C++14(g++5.4) 解法, 执行用时: 877ms, 内存消耗: 12892K, 提交时间: 2018-11-15 14:56:41

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 4000010;
const ll mod = 998244353;
const ll g = 3;

int R[maxn], BIT;

ll Pow(ll x, ll y){
	ll res = 1;
	for( ; y; x = (x * x) % mod, y >>= 1) if(y & 1) res = (res * x) % mod;
	return res;
}

ll ni(ll x){
	return Pow(x, mod-2);
}

void ntt(ll *a, int n, int inv){
	if(R[n-1] != n-1) for(int i = 0; i < n; i ++) R[i] = (R[i>>1]>>1) | ((i&1)<<(BIT-1));
	for(int i = 0; i < n; i ++) if(i < R[i]) swap(a[i], a[R[i]]);
	for(int i = 1; i < n; i <<= 1){
		ll mi = inv == 1 ? Pow(g, (mod-1)/(2*i)) : ni(Pow(g, (mod-1)/(2*i)));
		for(int j = 0; j < n; j += (i<<1)){
			ll x = 1;
			for(int k = 0; k < i; k ++, x = (x * mi) % mod){
				ll t1 = a[j+k], t2 = (x * a[j+k+i]) % mod;
				a[j+k] = (t1 + t2) % mod, a[j+k+i] = (t1 - t2) % mod; 
			}
		}
	}
}

ll n, m;
ll a[maxn], res;
int main(){
	scanf("%lld%lld", &n, &m);
	BIT = m, m = (1<<m);
	for(int i = 0; i < m; i ++) a[i] = Pow(2*Pow(g, (i*(mod-1))/m) + 1, n);
	ntt(a, m, -1);
	for(int i = 0; i < m; i ++) a[i] = (a[i] * ni(m)) % mod;
	for(int i = 0; i < m; i ++) res = (res + a[i] * Pow(2222303LL, i)) % mod;
	printf("%lld\n", (res%mod + mod) % mod);
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 513ms, 内存消耗: 12604K, 提交时间: 2022-11-02 12:32:02

#include<cstdio>
#include<algorithm>
const int p=119<<23|1;
constexpr long long fp(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1)ans=(ans*a)%p;
		a=(a*a)%p,b>>=1;
	}
	return ans;
}
constexpr int g=3,ig=fp(3,p-2);
class _FNTT
{
	int r[1<<20],lim;
public:
	void init(int l)
	{
		lim=1<<l;for(int i=1;i<lim;i++)r[i]=r[i>>1]>>1|(i&1)<<l-1;
	}
	void operator()(long long*a,int type)
	{
		for(int i=0;i<lim;i++)if(i<r[i])std::swap(a[i],a[r[i]]);
		for(int mid=1;mid<lim;mid<<=1)
		{
			long long on=fp(type==1?g:ig,(p-1)/mid>>1);
			for(int j=0;j<lim;j+=mid<<1)
			{
				long long o=1;
				for(int k=0;k<mid;k++,o=o*on%p)
				{
					long long x=a[j+k],y=a[j+k+mid]*o%p;
					a[j+k]=(x+y)%p,a[j+k+mid]=(x-y+p)%p;
				}
			}
		}
		if(type==-1)
		{
			long long inv=fp(lim,p-2);
			for(int i=0;i<lim;i++)a[i]=a[i]*inv%p;
		}
	}
}NTT;
long long a[1<<20];
int main()
{
	long long n;int m;scanf("%lld%d",&n,&m);
	const long long mul=2222303ll;long long ans=0;
	a[0]=1,a[1]=2;NTT.init(m);m=1<<m;
	NTT(a,1);for(int i=0;i<m;i++)a[i]=fp(a[i],n);
	NTT(a,-1);for(int i=m-1;i>=0;i--)ans=(ans*mul+a[i])%p;
	printf("%lld",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 530ms, 内存消耗: 10828K, 提交时间: 2018-04-21 07:23:07

#include<bits/stdc++.h>
using namespace std;
#define N 1100000
#define mo 998244353
int Pow(int x,long long y){
	int res=1;
	while (y>0){
		if (y&1){
			res=1LL*res*x%mo;
		}
		y>>=1;
		x=1LL*x*x%mo;
	}
	return res;
}
int A[N],Rev[N],n,w[N];
void DFT(int *A,int p){
	int i,j,k;
	for (i=0;i<n;i++){
		if (i<Rev[i]){
			swap(A[i],A[Rev[i]]);
		}
	}
	w[0]=1;
	for (i=1;i<n;i<<=1){
		int wn=Pow(3,mo-1+p*(mo-1)/(i<<1));
		for (j=i-2;j>=0;j-=2){
			w[j]=w[j>>1];
			w[j+1]=1LL*wn*w[j]%mo;
		}
		for (j=0;j<n;j+=(i<<1)){
			int *f=A+j,*g=A+j+i;
			for (k=0;k<i;k++){
				int x=1LL*w[k]*g[k]%mo;
				g[k]=(f[k]-x+mo)%mo,f[k]=(f[k]+x)%mo;
			}
		}
	}
}
int main(){
	long long t;
	int m,i;
	scanf("%lld%d",&t,&m);
	n=1<<m;
	for (i=0;i<n;i++){
		Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(m-1));
	}
	A[0]=1,A[1]=2;
	DFT(A,1);
	for (i=0;i<n;i++){
		A[i]=Pow(A[i],t);
	}
	DFT(A,-1);
	int Ans=0,now=1;
	for (i=0;i<n;i++){
		Ans=(Ans+1LL*A[i]*now%mo)%mo;
		now=1LL*now*2222303%mo;
	}
	printf("%lld\n",1LL*Ans*Pow(n,mo-2)%mo);
	return 0;
}

详情