結果

問題 No.1066 #いろいろな色 / Red and Blue and more various colors (Easy)
ユーザー carrot46carrot46
提出日時 2020-05-29 23:02:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,504 bytes
コンパイル時間 2,059 ms
コンパイル使用メモリ 184,112 KB
実行使用メモリ 5,932 KB
最終ジャッジ日時 2024-04-24 00:46:42
合計ジャッジ時間 3,853 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 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 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
    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