test/yosupo_Bitwise_Xor_Convolution.test.cpp

View this file on GitHub
Last update: 2023-07-16 21:56:51+09:00
Problem: https://judge.yosupo.jp/problem/bitwise_xor_convolution

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution"

#include "../template.hpp"

#include "../type/modint.hpp"

#include "../Math/XorConvolution.hpp"

using mint=ModInt<998244353>;

signed main(){
    int n;cin>>n;
    vector<mint> a(1<<n),b(1<<n);
    cin>>a>>b;
    cout<<XorConvolution(a,b)<<endl;
    return 0;
}

#line 1 "test/yosupo_Bitwise_Xor_Convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution"

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/yosupo_Bitwise_Xor_Convolution.test.cpp"

#line 1 "type/modint.hpp"
template<int Mod>
struct ModInt{
    int x;
    ModInt():x(0){}
    ModInt(int y): x (y >= 0 ? y % Mod : (Mod - (-y) % Mod) % Mod){}
    ModInt(long long y){
        if (y >= 0)
        {
            x = (int)(y % (ll)(Mod));
        }
        else
        {
            int tmp = (int)((-y) % (ll)Mod);
            x = (Mod - tmp) % Mod;
        }
    }
    ModInt &operator+=(const ModInt &p){
        if((x += p.x) >= Mod) x -= Mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p){
        if((x += Mod - p.x) >= Mod) x -= Mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p){
        x = (int)(1ll * x * p.x % Mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p){
        (*this) *= p.inverse();
        return *this;
    }
    ModInt operator-()const{return ModInt(-x);}
    ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
    ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
    ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
    ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
    bool operator==(const ModInt &p)const{return x==p.x;}
    bool operator!=(const ModInt &p)const{return x!=p.x;}
    ModInt inverse()const{
        int a = x, b = Mod ,u = 1, v = 0, t;
        while(b>0){
            t=a/b;
            swap(a-=t*b,b);swap(u-=t*v,v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n)const{
        ModInt ret(1),mul(x);
        while(n>0){
            if(n&1) ret*=mul;
            mul*=mul;n>>=1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os,const ModInt &p){return os<<p.x;}
    friend istream &operator>>(istream &is,ModInt &a){long long t;is>>t;a=ModInt<Mod>(t);return (is);}
    static int get_mod(){return Mod;}
};
#line 6 "test/yosupo_Bitwise_Xor_Convolution.test.cpp"

#line 1 "Math/XorConvolution.hpp"
// ret_k = sum a_i * b_j, i^j=k
template<typename T>
vector<T> XorConvolution(vector<T> a,vector<T> b){
    assert(a.size()==b.size());
    int n=(int)a.size();
    vector<T> ret(n);
    // FWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0){
            {
                T x=a[j],y=a[j|i];
                a[j]=x+y,a[j|i]=x-y;
            }
            {
                T x=b[j],y=b[j|i];
                b[j]=x+y,b[j|i]=x-y;
            }
        }
    }
    for(int i=0;i<n;i++) ret[i]=a[i]*b[i];
    // IFWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0){
            T x=ret[j],y=ret[j|i];
            ret[j]=(x+y)/2,ret[j|i]=(x-y)/2;
        }
    }
    return ret;
}
#line 8 "test/yosupo_Bitwise_Xor_Convolution.test.cpp"

using mint=ModInt<998244353>;

signed main(){
    int n;cin>>n;
    vector<mint> a(1<<n),b(1<<n);
    cin>>a>>b;
    cout<<XorConvolution(a,b)<<endl;
    return 0;
}