牛客练习赛80 -- 卷积

题目链接: https://ac.nowcoder.com/acm/contest/11170/B
思维题:观察可知c数组只需计算前3项，c[3]~c[n - 1]均为0,故只需分析前三项的情况即可
c0 = (sa[n - 1] - sa[0]) * (sb[n - 1] - sb[0]);
c1 = (a[0] * b[0]) + a[0] * (sb[n - 1] - sb[1]) + b[0] * (sa[n - 1] - sa[1]);
c2 = (a[0] * b[1]) + (a[1] * b[0]);
[注]:sa,sb为a,b数组前缀和

代码细节：减法取模操作 -- 化正取模
(arr[n] - arr[1] + MOD) % MOD
推荐代码

#include <bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=998244353 ;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
ll arr[MAXN],brr[MAXN],c[MAXN];
int main(){
    ios;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++) cin>>brr[i];
    int c1,c2,c0;
    c2=(arr[1]*brr[2]%MOD+arr[2]*brr[1]%MOD)%MOD;
    for(int i=1;i<=n;i++) arr[i]=(arr[i]+arr[i-1])%MOD;
    for(int i=2;i<=n;i++) brr[i]=(brr[i]+brr[i-1])%MOD;
    c1=((arr[1]*((brr[n]-brr[2]+MOD)%MOD)%MOD+brr[1]*((arr[n]-arr[2]+MOD)%MOD)%MOD)%MOD+(arr[1]*brr[1])%MOD)%MOD;

    c0=(arr[n]-arr[1]+MOD)%MOD*((brr[n]-brr[1]+MOD)%MOD)%MOD;
//     c[1] = (((a[0] * b[0]) % mod + a[0] * (sb[n - 1] - sb[1]) % mod) % mod + b[0] * (sa[n - 1] - sa[1]) % mod) % mod;

    c[0]=c0;
    c[1]=c1;
    c[2]=c2;
    for(int i=0;i<n;i++) cout<<c[i]<<' ';
    return 0;
}

AC代码(不推荐__int128)

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define debug system("pause")
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
__int128 read() {
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x = x * 10 + ch -'0'; ch = getchar(); }
    return x * f;
}
void write(__int128 x) {
    if(x<0) { putchar('-'); x = -x; }
    if(x>9) write(x/10);  putchar(x % 10 + '0');
}

const int N = 1e5 + 10, mod = 998244353;
int n;
ll a[N], b[N];
__int128 sa[N], sb[N];
__int128 c0, c1, c2;
int c[N];

int main() {
    cin >> n;
    rep(i, 0, n - 1) {
        a[i] = read();
        if(i == 0) sa[i] = a[i];
        else sa[i] = (sa[i - 1] + a[i]);
    }    
    rep(i, 0, n - 1) {
        b[i] = read();
        if(i == 0) sb[i] = b[i];
        else sb[i] = (sb[i - 1] + b[i]);
    }
    c0 = (sa[n - 1] - sa[0]) * (sb[n - 1] - sb[0]);
    c1 = (a[0] * b[0]) + a[0] * (sb[n - 1] - sb[1]) + b[0] * (sa[n - 1] - sa[1]);
    c2 = (a[0] * b[1]) + (a[1] * b[0]);
    c0 %= mod; c1 %= mod; c2 %= mod;
    if(n >= 1) {
        write(c0); cout << ' ';
    }
    if(n >= 2)  {
        write(c1); cout << ' '; 
    }
    if(n >= 3) {
        write(c2); cout << ' ';
    }
    rep(i, 3, n - 1) cout << "0 ";
    cout << endl;

    return 0;
}