我写出了如下两份代码,一份可以 AC,一份会 RE。
AC 代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N (1<<18)+20
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define cpx complex<double>
#define poly vector<ll>
#define it vector<ll>::iterator
const ll mod = 998244353,yk = 3,yi = 332748118;
inline ll qpow(ll base,ll e){
ll res = 1;
while(e){
res= (e&1) ? res * base % mod : res;
base = base * base % mod;
e >>= 1;
}
return res;
}
int n,m,ln,rto[N];ll n1,n2,ayk[N];
poly a,b,d;
inline poly get(const int &n){poly ans(n+1);return ans;}
inline poly operator%(poly a,const int &x){a.resize(x,0);return a;}
inline poly operator-(poly a,poly b){
int n = max(a.size(),b.size());
a.resize(n),b.resize(n);
poly c = get(n-1);
for(int i = 0;i < n;++i)c[i] = (a[i] - b[i] + mod)%mod;
return c;
}
inline void init(const int &n){for(int i = 1;i <= n;++i)rto[i] = (rto[i>>1]>>1)|(i&1?n>>1:0);}
inline void ntt(poly &a,const int &n){
for(int i = 0;i < n;++i)if(rto[i]<i)swap(a[rto[i]],a[i]);
for(int gap = 2,mid = 1;gap <= n;gap <<= 1,mid <<= 1){
for(int i = 0;i < n;i += gap){
ll wk = 1,wn = ayk[gap];
for(int j = i;j < i+mid;++j){
n1 = a[j],n2 = a[j+mid];
a[j] = (n1+n2*wk)%mod,a[j+mid] = (n1-n2*wk%mod+mod)%mod;
wk = wk * wn % mod;
}
}
}
}
inline poly operator*(poly a,poly b){
int m = a.size()+b.size()-2,n = 1;
for(;n<=m;n<<=1);
a.resize(n),b.resize(n);
init(n),ntt(a,n),ntt(b,n);
for(int i = 0;i < n;++i)a[i] = a[i]*b[i]%mod;
ntt(a,n);
ll inv = qpow(n,mod-2);
poly c = get(m);
c[0] = a[0]*inv%mod;
for(int i = 1;i <= m;++i)c[i] = a[n-i]*inv%mod;
return c;
}
// 主函数
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;--n;a = get(n);
for(int i = 1;i<=n;++i)cin >> a[i],a[i] = (!a[i]?0:mod - a[i]);a[0] = 1;
for(ln = 1;(ln<<1)<N;ln <<= 1);
ayk[ln] = qpow(3,(mod-1)/ln);
for(ln>>=1;ln;ln>>=1)ayk[ln] = (ayk[ln<<1]*ayk[ln<<1]%mod);
b = get(0),d = get(0),b[0] = qpow(a[0],mod-2),d[0] = 2;
int m = 1;
do{
m <<= 1;
b = (b*(d-(a%m)*b))%m;
// for(int i = 0;i < m;++i)cout << b[i] << ' '; cout << '\n';
}while(m<=n);
for(int i = 0;i <= n;++i)cout << b[i] << ' ';
// cout << flush,system("pause"); // 交之前一定要把这一行注释掉!!!!!!!
return 0;
}
RE 代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N (1<<18)+20
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define cpx complex<double>
#define poly vector<ll>
const ll mod = 998244353,yk = 3;
poly g,f,d;int n,rto[N],ln;ll ayk[N],wk,wn,n1,n2;
inline ll qpow(ll base,ll e){
ll res = 1;
while(e){
if(e&1)res = res * base % mod;
base = base * base % mod;
e >>= 1;
}
return res;
}
inline poly get(const int &n){poly ans(n+1);return ans;}
inline void init(const int &n){for(int i = 1;i < n;++i)rto[i] = (rto[i>>1]>>1|(i&1?n>>1:0));}
inline void ntt(poly &a,const int &n){
for(int i = 0;i < n;++i)if(rto[i]<i)swap(a[rto[i]],a[i]);
for(int gap = 2,mid = 1;gap <= n;gap <<= 1,mid <<= 1){
for(int i = 0;i < n;i += gap){
wk = 1,wn = ayk[gap];
for(int j = i;j < i+mid;++j){
n1 = a[j],n2 = a[j+mid];
a[j] = (n1+n2*wk)%mod,a[j+mid] = (n1-n2*wk%mod+mod)%mod;
wk = wk * wn % mod;
}
}
}
}
inline poly operator%(poly a,const int &x){
a.resize(x,0);
return a;
}
inline poly operator-(poly a,poly b){
// printf("ope- in\n");
int n = max(a.size(),b.size());
a.resize(n),b.resize(n);
poly c = get(n-1);
for(int i = 0;i <= n;++i)c[i] = (a[i]-b[i]+mod)%mod;
// printf("ope- out\n");
return c;
}
inline poly operator*(poly a,poly b){
int m = a.size()+b.size()-2,n = 1;
for(;n<=m;n<<=1);
a.resize(n),b.resize(n);
init(n),ntt(a,n),ntt(b,n);
for(int i = 0;i < n;++i)a[i] = a[i]*b[i]%mod;
ntt(a,n);
ll inv = qpow(n,mod-2);
poly c = get(m);
c[0] = a[0]*inv%mod;
for(int i = 1;i <= m;++i)c[i] = a[n-i]*inv%mod;
return c;
}
// 主函数
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;--n;g = get(n);g[0] = 1;
for(int i = 1;i <= n;++i)cin >> g[i],g[i] = (!g[i]?0:mod - g[i]);
for(ln = 1;(ln << 1) < N;ln <<= 1);
ayk[ln] = qpow(3,(mod-1)/ln);
for(ln >>= 1;ln;ln >>= 1)ayk[ln] = (ayk[ln<<1]*ayk[ln<<1])%mod;
f = get(0),d = get(0);
f[0] = qpow(g[0],mod-2),d[0] = 2;
// 计算
int m = 1;
do{
m<<=1;
f = f*(d-(g%m)*f)%m;
}while(m <= n);
for(int i = 0;i <= n;++i)cout << f[i] << ' ';
// cout << flush,system("pause"); // 交之前一定要把这一行注释掉!!!!!!!
return 0;
}
另外,RE 代码与 AC 代码在 Dev-C++ 上测试样例没有区别,但是在 VSCode 上,RE 代码会意外断点。
我无法比较出这两份代码的差别。请万能的谷友帮帮忙,orz