結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー carrot46carrot46
提出日時 2020-05-29 22:57:57
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
84,604 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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