結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー harady_a_humanharady_a_human
提出日時 2020-05-01 17:29:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,751 bytes
コンパイル時間 2,051 ms
コンパイル使用メモリ 182,700 KB
実行使用メモリ 28,928 KB
最終ジャッジ日時 2024-11-06 01:59:45
合計ジャッジ時間 27,452 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 3 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::vector<int> saiki(int, int)':
main.cpp:88:47: warning: narrowing conversion of 'A.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)l))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   88 |     if (r == l + 1) return vector<int>{A[l], 1};
      |                                               ^
main.cpp:88:47: warning: narrowing conversion of 'A.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)l))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]

ソースコード

diff # 

//FFTはふるやん氏の実装をお借りしました
//↓↓↓ふるやんさんのブログ↓↓↓
//https://www.creativ.xyz/fast-fourier-transform/


#include <bits/stdc++.h>
 
using namespace std;

#define pb push_back
#define eb emplace_back
#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

using ll = long long;
const ll mod = 10007;

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<ll> 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(((ll)(elm+(Double)0.5))%mod);
    }
    return ret;
}
 
signed main() {
    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;
    }
}
0