結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー autumn-eelautumn-eel
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0