結果

問題 No.1503 Bitwise And Convolution Twisted
ユーザー chineristAC
提出日時 2021-05-07 23:13:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 846 ms / 2,000 ms
コード長 2,559 bytes
コンパイル時間 4,623 ms
コンパイル使用メモリ 211,584 KB
最終ジャッジ日時 2025-01-21 08:46:29
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n,c) for (int i=0;i<n;i+=c)
#define append push_back
#define all(x) (x).begin(), (x).end()

template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using piil = tuple<ll,int,int>;

template<class T>
inline bool chmin(T &a, T b){
  if (a>b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
inline bool chmax(T &a, T b){
  if (a<b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
T sum(vec<T> x){
  T res=0;
  for (auto e:x){
    res += e;
  }
  return res;
}

using mint = modint998244353;

void printv(vec<mint> x){
  cout<<"{";
  for (auto e:x){
    cout<<e.val()<<" ";
  }
  cout<<"}\n";
}





vector<mint> subset(int n,vector<mint> X){
  if (n==0){
    return X;
  }
  vector<mint> Y(1<<(n-1));
  vector<mint> Z(1<<(n-1));
  for (int i=0;i<(1<<(n-1));i++){
    Y[i] = X[i];
    Z[i] = X[i+(1<<(n-1))];
  }
  auto Y1 = subset(n-1,Y);
  auto Z1 = subset(n-1,Z);
  for (int i=0;i<(1<<(n-1));i++){
    X[i] = Y1[i];
    X[i+(1<<(n-1))] = Y1[i] + Z1[i];
  }
  return X;
}

vector<mint> isubset(int n,vector<mint> X){
  if (n==0){
    return X;
  }
  vector<mint> Y(1<<(n-1));
  vector<mint> Z(1<<(n-1));
  for (int i=0;i<(1<<(n-1));i++){
    Y[i] = X[i];
    Z[i] = X[i+(1<<(n-1))];
  }
  auto Y1 = isubset(n-1,Y);
  auto Z1 = isubset(n-1,Z);
  for (int i=0;i<(1<<(n-1));i++){
    X[i] = Y1[i];
    X[i+(1<<(n-1))] = Z1[i] - Y1[i];
  }
  return X;
}

const ll INF = 1e17;

int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n,a,b;
  cin>>n;
  vector<mint> A(1<<n);
  vector<mint> B(1<<n);
  for (int i=0;i<(1<<n);i++){
    cin>>a;
    A[(1<<n)-1-i] = (mint)(a);
  }
  for (int i=0;i<(1<<n);i++){
    cin>>b;
    B[i] = (mint)(b);
  }

  auto A1 = subset(n,A);
  reverse(all(A1));

  auto B1 = isubset(n,B);
  
  vector<mint> C(1<<n);
  for (int i=0;i<(1<<n);i++){
    C[i] = A1[i] * B1[i];
  }
  auto C1 = subset(n,C);
  for (int i=0;i<(1<<n);i++){
    cout<<C1[i].val();
    if (i!=(1<<n)-1){
      cout<<" ";
    }
    else{
      cout<<"\n";
    }
  }
}
0