結果
| 問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
| ユーザー |
 harady_a_human
|
| 提出日時 | 2020-05-01 16:39:44 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,717 bytes |
| コンパイル時間 | 2,230 ms |
| コンパイル使用メモリ | 183,988 KB |
| 実行使用メモリ | 30,188 KB |
| 最終ジャッジ日時 | 2024-11-06 01:55:15 |
| 合計ジャッジ時間 | 26,162 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 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 | 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 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | AC | 2 ms
6,816 KB |
ソースコード
// #pragma GCC target("avx") // CPU 処理並列化
// #pragma GCC optimize("O3") // CPU 処理並列化
// #pragma GCC optimize("unroll-loops") // 条件処理の呼び出しを減らす
#include <bits/stdc++.h>
#include <complex>
// #include <iostream> // cout, endl, cin
// #include <string> // string, to_string, stoi
// #include <vector> // vector
// #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
// #include <utility> // pair, make_pair
// #include <tuple> // tuple, make_tuple
// #include <cstdint> // int64_t, int*_t
// #include <cstdio> // printf
// #include <map> // map
// #include <queue> // queue, priority_queue
// #include <set> // set
// #include <stack> // stack
// #include <deque> // deque
// #include <unordered_map> // unordered_map
// #include <unordered_set> // unordered_set
// #include <bitset> // bitset
// #include <climits>
// #include <cmath>
// #include <iomanip>
// #include <functional>
// #include <numeric>
// #include <random>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
// #define F first
// #define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end())
#define Double double
// #define endl '\n'
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using ll = long long;
using UnWeightedGraph = vector<vector<int>>;
ll INF = LLONG_MAX / 4 - 100;
int IINF = INT_MAX / 4;
ll mod = 1e9 + 7;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
long double pi = 3.141592653589793238;
class fact {
public:
long long fmod = 1e9+7;
vector<long long> fac, finv, inv;
fact (int n, long long Mod = 1e9+7) {
fmod = Mod;
fac = vector<long long>(n + 1, 0);
finv = vector<long long>(n + 1, 0);
inv = vector<long long>(n + 1, 0);
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < n + 1; i++) {
fac[i] = fac[i-1] * i % fmod;
inv[i] = mod - inv[mod%i] * (mod/i) % mod;
finv[i] = finv[i-1] * inv[i] % mod;
}
}
ll nCr(ll n, ll r) {if(n < r) return 0; return fac[n] * finv[r] % fmod * finv[n-r] % fmod;}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
inline int operator [] (int i) {return fac[i];}
ll DeBuG(ll n, ll r);
};
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return (a / GCD(a, b)) * (b / GCD(a, b)) * GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1]; for (int i = 0; i < n + 1; i++) {a[i] = 1;}for (int i = 2; i < n + 1; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
double dis(int x1, int x2, int y1, int y2) {
return sqrt((double)abs(x1-x2)*(double)abs(x1-x2)+(double)abs(y1-y2)*(double)abs(y1-y2));
}
int ceili(int x, int y) {
if (x % y == 0) return x / y;
else return x / y + 1;
}
unsigned int randxor() {
static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
unsigned int t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
uint64_t xor64(void) {
static uint64_t x = 88172645463325252ULL;
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
vector<complex<Double>> fft(vector<complex<Double>> a, bool inverse = false) {
int n = a.size();
int h = 0; // h = log_2(n)
for (int i = 0; 1 << i < n; i++) h++;
// バタフライ演算用の配置入れ替え
for (int i = 0; i < n; i++) {
int j = 0;
for (int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);
if (i < j) swap(a[i], a[j]);
}
// バタフライ演算
for (int b = 1; b < n; b *= 2) {
// 第 log_2(b) + 1 段
// ブロックサイズ = b * 2
for (int j = 0; j < b; j++) {
// ブロック内 j 個目
// 重み w = (1 の原始 2b 乗根の j 乗)
complex<Double> w =
polar((Double)1.0, (2 * (Double)M_PI) / (2 * b) * j * (inverse ? 1 : -1));
for (int k = 0; k < n; k += b * 2) {
// k を先頭とするブロック
complex<Double> s = a[j + k]; // 前
complex<Double> t = a[j + k + b] * w; // 後
a[j + k] = s + t; // 前の更新
a[j + k + b] = s - t; // 後の更新
}
}
}
// 逆変換時にサイズで割る調整
if (inverse)
for (int i = 0; i < n; i++) a[i] /= n;
return a;
}
// Cooley–Tukey FFT algorithm O(N log N)
vector<complex<Double>> fft(vector<Double> a, bool inverse = false) {
vector<complex<Double>> a_complex(a.size());
for (int i = 0; i < a.size(); i++) a_complex[i] = complex<Double>(a[i], 0);
return fft(a_complex, inverse);
}
// FFT による畳み込み O(N log N)
vector<Double> convolve(vector<Double> a, vector<Double> b) {
int s = a.size() + b.size() - 1; // 畳み込み結果のサイズ
int t = 1; // FFT に使う配列のサイズ（2 の累乗）
while (t < s) t *= 2;
a.resize(t); // FFT するためにリサイズ
b.resize(t); // FFT するためにリサイズ
vector<complex<Double>> A = fft(a);
vector<complex<Double>> B = fft(b);
for (int i = 0; i < t; i++) {
A[i] *= B[i]; // 畳み込み結果の FFT 結果を得る
}
A = fft(A, true); // IFFT で畳み込み結果を得る
a.resize(s); // 畳み込み結果を入れるためにリサイズ
for (int i = 0; i < s; i++) a[i] = A[i].real(); // 実部が答え
return a;
}
vector<int> A;
vector<int> saiki(int l, int r) {
if (r == l + 1) return vector<int>{A[l], 1};
vector<int> tL = saiki(l, (l+r)/2), tR = saiki((l+r)/2, r);
vector<Double> L, R;
for (auto &&elm : tL) L.pb(elm);
for (auto &&elm : tR) R.pb(elm);
auto res = convolve(L, R);
vector<int> ret;
for (auto &&elm : res) {
ret.pb(((int)(elm+(Double)0.5))%mod);
// if (ret.back() < 0) {
// FOR (i, l, r) cout << A[i] << " "; cout << endl;
// rep (i, r-l+1) cout << res[i] << " "; cout << endl;
// exit(0);
// }
}
return ret;
}
void solve() {
mod = 10007;
int n; cin >> n; int m; cin >> m;
A.resize(n); rep (i, n) cin >> A[i], A[i]--, A[i] %= mod;
auto ans = saiki(0, n);
rep (i, m) {
int a; cin >> a;
cout << ans[a] << endl;
}
}
signed main() {
clock_t start = clock();
cin.tie(0);
ios::sync_with_stdio(false);
solve();
clock_t now = clock();
// cout << (double)(now-start)/CLOCKS_PER_SEC << endl;
}