結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー carrot46
提出日時 2020-05-29 22:57:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,523 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 189,320 KB
実行使用メモリ 84,604 KB
最終ジャッジ日時 2024-11-06 07:12:32
合計ジャッジ時間 8,598 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 10 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<62);
typedef complex<double> cm;
typedef vector<cm> vcm;

#define pi 3.1415926535

vcm dft(int n, vcm f, bool inv){
    if(n == 1) return f;
    int n2 = n / 2;
    vcm f1(n2), f2(n2);
    rep(i,n) (!(i & 1) ? f1[i/2] : f2[i/2]) = f[i];
    f1 = dft(n2, f1, inv);
    f2 = dft(n2, f2, inv);
    cm zeta = polar(1.0, (inv ? -2.0 : 2.0) * pi / n);
    cm pow_zeta = cm(1);
    rep(i, n2){
        f[i] = f1[i] + pow_zeta * f2[i];
        pow_zeta *= zeta;
    }
    if(pow_zeta.real() > -0.99) cout<<inv<<endl;
    rep(i, n2){
        f[i + n2] = f1[i] + pow_zeta * f2[i];
        pow_zeta *= zeta;
    }
    return f;
}

vcm convolution(vcm g,vcm h){
    int sz = g.size() + h.size() - 1, n = 1;
    while(sz > n) n *= 2;
    g.resize(n);
    h.resize(n);
    vcm g_hat = dft(n, g, false), h_hat = dft(n, h, false);
    vcm gh_hat(n);
    rep(i,n) gh_hat[i] = g_hat[i] * h_hat[i];
    vcm gh = dft(n, gh_hat, true);
    rep(i, n) gh[i] /= cm(n);
    gh.resize(sz);
    return gh;
}
int main() {
    cin>>N>>Q;
    vec a(N);
    rep(i,N) {
        cin>>a[i];
        --a[i];
    }
    const int max_log = 18, max_N = (1LL<<18);
    const ll mod = 998244353;
    vector<mat> vs(max_log + 1, mat(0));
    rep(i,N) vs[0].push_back({1, a[i]});
    int last = max_log;
    rep(i,max_log){
        if(vs[i].size() == 1) {
            last = i;
            break;
        }
        rep(j, vs[i].size() / 2){
            vector<vcm> temp(2, vcm(0));
            rep(k,2) for(ll v : vs[i][j * 2 + k]) temp[k].emplace_back(v);
            vcm res = convolution(temp[0], temp[1]);
            vec pu(0);
            //cout<<j<<endl;
            rep(k, res.size()) {
                pu.push_back((ll)(res[k].real() + 0.5) % mod);
                //cout<<pu[k]<<endl;
            }
            //cout<<endl;
            vs[i+1].push_back(pu);
        }
        if(vs[i].size() & 1) vs[i+1].push_back(vs[i][(vs[i].size() + 1) / 2]);
    }
    reverse(ALL(vs[last][0]));
    rep(i,Q){
        cin>>A;
        cout<<vs[last][0][A]<<endl;
    }
}
0