RE 代码玄关求助
查看原帖
RE 代码玄关求助
1007758
Nasaepa楼主2025/7/3 15:38

我写出了如下两份代码,一份可以 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;
}

AC 记录

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 记录

另外,RE 代码与 AC 代码在 Dev-C++ 上测试样例没有区别,但是在 VSCode 上,RE 代码会意外断点。

我无法比较出这两份代码的差别。请万能的谷友帮帮忙,orz

2025/7/3 15:38
加载中...