結果
問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
ユーザー | 沙耶花 |
提出日時 | 2020-05-29 21:52:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,189 ms / 3,500 ms |
コード長 | 2,091 bytes |
コンパイル時間 | 3,467 ms |
コンパイル使用メモリ | 210,400 KB |
最終ジャッジ日時 | 2025-01-10 17:03:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:119:29: warning: narrowing conversion of ‘(A.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) % 998244353)’ from ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} to ‘int’ [-Wnarrowing] 119 | X[i] = {A[i]%modulo,1}; main.cpp:119:29: warning: narrowing conversion of ‘(A.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) % 998244353)’ from ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} to ‘int’ [-Wnarrowing] main.cpp:114:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 114 | for(int i=0;i<N;i++)scanf("%lld",&A[i]); | ~~~~~^~~~~~~~~~~~~~ main.cpp:138:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 138 | for(int i=0;i<Q;i++)scanf("%d",&B[i]); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 10000000000000000 //aのb乗 int beki(int a,int b){ int x = 1; while(b!=0){ if(b&1){ x=mod(x*a); } a=mod(a*a); b>>=1; } return x; } //aの逆元 int gyakugen(int a){ return beki(a,modulo-2); } void NTT(vector<int> &A){ int n = A.size(); vector<int> tmp(n,0); int mask = n-1; for(int i=n>>1;i>=1;i>>=1){ int r = (modulo-1)/n; r *= i; int w = beki(3,r); int now = 1; for(int j=0;j<n;j+=i){ for(int k=0;k<i;k++){ tmp[j+k] = mod(A[((j<<1)&mask)|k] + mod(now*A[(((j << 1)|i)&mask)|k])); } now = mod(now * w); } swap(A,tmp); } int num; for(int i=0;true;i++){ if((n>>i)&1){ num = i; break; } } if(num&1){ swap(A,tmp); for(int i=0;i<n;i++)A[i] = tmp[i]; } return; } vector<int> do_NTT(vector<int> A,vector<int> B){ int n = A.size()+B.size()-1; if(min(A.size(),B.size())<=150){ vector<int> ret(n,0); for(int i=0;i<A.size();i++){ for(int j=0;j<B.size();j++){ ret[i+j] = mod(ret[i+j] + mod(A[i]*B[j])); } } return ret; } for(int i=0;true;i++){ if((1<<i)>=n){ n = (1<<i); break; } } A.resize(n),B.resize(n); bool f = A==B; NTT(A); if(f)B=A; else NTT(B); int rev = gyakugen(n); vector<int> c(n); for(int i=0;i<n;i++)c[i] = mod(mod(A[i]*B[i])*rev); reverse(c.begin()+1,c.end()); NTT(c); return c; } int main(){ int N,Q; cin>>N>>Q; vector<long long> A(N); for(int i=0;i<N;i++)scanf("%lld",&A[i]); vector<vector<int>> X(N); for(int i=0;i<N;i++){ A[i]--; X[i] = {A[i]%modulo,1}; } while(X.size()!=1){ vector<vector<int>> Y; for(int i=0;i<X.size();i+=2){ if(i+1!=X.size()){ Y.push_back(do_NTT(X[i],X[i+1])); } else{ Y.push_back(X[i]); } } X = Y; reverse(X.begin(),X.end()); } vector<int> B(Q); for(int i=0;i<Q;i++)scanf("%d",&B[i]); for(int i=0;i<B.size();i++){ if(X[0].size()<=B[i])printf("0\n"); else printf("%d\n",X[0][B[i]]); } return 0; }