結果
問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
ユーザー |
|
提出日時 | 2020-05-29 22:47:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,412 bytes |
コンパイル時間 | 1,931 ms |
コンパイル使用メモリ | 181,148 KB |
実行使用メモリ | 31,020 KB |
最終ジャッジ日時 | 2024-11-06 06:53:23 |
合計ジャッジ時間 | 42,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 16 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n)for(int i=0;i<(n);i++)using namespace std;typedef long long ll;const int MOD=998244353;const int r=3;ll ppow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}void dft(vector<ll>&f,bool inv=false){int n=f.size();rep(i,n){int b=31-__builtin_clz(n);int j=0;rep(k,b){if(i>>k&1)j|=1<<(b-k-1);}if(i<j)swap(f[i],f[j]);}for(int i=2;i<=n;i<<=1){ll w=ppow(r,(MOD-1)/i);if(inv)w=ppow(w,MOD-2);for(int k=0;k<n;k+=i){ll x=1;rep(j,i/2){ll t=x*f[k+j+i/2]%MOD,u=f[k+j];f[k+j]=(u+t)%MOD;f[k+j+i/2]=(u+MOD-t)%MOD;(x*=w)%=MOD;}}}if(inv){ll n_inv=ppow(n,MOD-2);rep(i,n)(f[i]*=n_inv)%=MOD;}}vector<ll>multiply(vector<ll>A,vector<ll>B){int m=A.size()+B.size();int N=1;while(N<A.size()+B.size())N<<=1;A.resize(N);B.resize(N);dft(A,0);dft(B,0);vector<ll>f(N);rep(i,N)f[i]=A[i]*B[i]%MOD;dft(f,1);f.erase(f.begin()+m,f.end());return f;}int main(){int n,q;cin>>n>>q;vector<vector<ll>>vs;rep(i,n){int a;scanf("%d",&a);vs.push_back({a-1,1});}while(vs.size()>1){vector<vector<ll>>nx;for(int i=0;i+1<vs.size();i+=2){auto res=multiply(vs[i],vs[i+1]);if(i+2==vs.size()-1)res=multiply(res,vs[i+2]);nx.push_back(res);}vs=nx;}rep(i,q){int b;scanf("%d",&b);printf("%lld\n",vs[0][b]);}}