第16组输入数据出现乱码?!代码RE!
查看原帖
第16组输入数据出现乱码?!代码RE!
137437
PPL_楼主2021/2/20 19:30

大概是这个样子:

......
931472006 867810753 696740371 94958620 1011045]歼U?0`磕(?靊?未???悵u『摼H紟觎\li¦澀途?诐黶?嶕V疰Vo?h8b④覉輿?霻?霘卭9f?~鄻叧~硛郐0LL$鎛]l"[€wWN紞
埸αG駐艹MP\絼o盔晜DIl?睧U>趂}~f勤砘Wn畖詊愆|詅鳜蹻庯lFZ醧l?嚮??烹A釔;ONo3z廲幮T瀧?7渰裔?H餍?鐬餾?
......

不知道是我下载的问题还是什么,数据是这个样子,但我以前一份AC的代码依然可以AC,而我现在这份代码RE在了第16组:

//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std; 

typedef long long LL;
const int MAXN = 1 << 18 | 5;
const int MOD = 998244353;
const int PHI = 998244352;
const int G = 3;
const int GINV = 332748118;
int n;
int aa[MAXN],b[MAXN],c[MAXN];

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x);
	if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

int qpow(int x,int y)
{
	int ret = 1;
	while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
	return ret;
}

int rev[MAXN],N;
void pre(int x)
{
	N = 1; int l = -1;
	while(N <= (x<<1)) N <<= 1,l++;
	for(int i = 1;i < N;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l);
}
int Add(int x){if(x >= MOD) x -= MOD;return x;}
int Del(int x){if(x < 0) x += MOD;return x;}
void NTT(int *a,int opt,int len)
{
	for(int i = 0;i < len;++ i) if(i < rev[i]) swap(a[i],a[rev[i]]);
	for(int i = 1;i < len;i <<= 1)
	{
		int w = qpow(opt == 1 ? G : GINV,PHI / (i << 1));
		for(int j = 0,p = i << 1;j < len;j += p)
		{
			int mi = 1;
			for(int k = 0;k < i;++ k,mi = 1ll * mi * w % MOD)
			{
				int X = a[j+k],Y = 1ll * mi * a[i+j+k] % MOD;
				a[j+k] = Add(X+Y);
				a[i+j+k] = Del(X-Y);
			}
		}
	}
	if(opt == -1) 
	{
		int inv = qpow(len,MOD-2);
		for(int i = 0;i < len;++ i) a[i] = 1ll * a[i] * inv % MOD;
	}
}
void polyinv(int *f,int *g,int len)
{
	if(len == 1)
	{
		g[0] = qpow(f[0],MOD-2);
		return;
	}
	polyinv(f,g,len>>1);
	pre(len);
	for(int i = 0;i < len;++ i) c[i] = f[i];
	for(int i = len;i < N;++ i) c[i] = 0;
	NTT(c,1,N); NTT(g,1,N);
	for(int i = 0;i < N;++ i) g[i] = (((2ll * g[i] - 1ll * c[i] * g[i] % MOD * g[i]) % MOD) + MOD) % MOD;
	NTT(g,-1,N);
	for(int i = len;i < N;++ i) g[i] = 0;
}

signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read();
	for(int i = 0;i < n;++ i) aa[i] = Read();
	pre(n);
	polyinv(aa,b,N);
	for(int i = 0;i < n;++ i) Put(b[i],' ');
	return 0;
}
2021/2/20 19:30
加载中...