結果

問題 No.206 数の積集合を求めるクエリ
ユーザー codershifthcodershifth
提出日時 2016-01-16 20:06:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 229 ms / 7,000 ms
コード長 3,309 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 165,452 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2024-09-19 20:14:54
合計ジャッジ時間 4,830 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 7 ms
5,376 KB
testcase_13 AC 6 ms
5,376 KB
testcase_14 AC 7 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 7 ms
5,376 KB
testcase_17 AC 97 ms
14,592 KB
testcase_18 AC 88 ms
14,660 KB
testcase_19 AC 96 ms
14,592 KB
testcase_20 AC 87 ms
14,592 KB
testcase_21 AC 90 ms
14,720 KB
testcase_22 AC 92 ms
14,592 KB
testcase_23 AC 96 ms
14,592 KB
testcase_24 AC 229 ms
14,720 KB
testcase_25 AC 227 ms
14,592 KB
testcase_26 AC 217 ms
14,716 KB
testcase_27 AC 184 ms
14,592 KB
testcase_28 AC 221 ms
14,720 KB
testcase_29 AC 221 ms
14,564 KB
testcase_30 AC 219 ms
14,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

typedef std::complex<double> c_t;
// O(n*log(n))
// a.size() must be 2^k
void fft(std::vector<c_t> &a, int dir = 1)
{
        int n = a.size();
        int i = 0;
        for (int j = 0; j < n; ++j)
        {
            if (j < i)
                std::swap(a[i], a[j]);
            for (int k = (n>>1); k > (i ^= k); k >>= 1) ;
        }

        for (int s = 0; (1<<s) < n; ++s)
        {
            int m = 1 << s;
            c_t wm = std::polar(1.0, M_PI / m * dir), w(1.0);
            for (int j = 0; j < m; ++j)
            {
                for (int k = j; k < n; k += m * 2)
                {
                    c_t s = a[k], t = w * a[k + m];
                    a[k] = s + t;
                    a[k + m] = s - t;
                }
                w *= wm;
            }
        }
        if (dir < 0)
            for_each(a.begin(), a.end(), [n](c_t &v) {v /= n;});
}
void convolve(const std::vector<double> &a, const std::vector<double> &b, std::vector<double> &c)
{
        int n = a.size()+b.size()-1;
        int m = std::ceil(std::log2(n));
        std::vector<c_t> abuf((1<<m),0);
        std::vector<c_t> bbuf((1<<m),0);
        // padding
        for (size_t i = 0; i < a.size(); ++i)
            abuf[i+b.size()-1] = c_t(a[i],0);
        // reverse
        for (size_t i = 0; i < b.size(); ++i)
            bbuf[i] = c_t(b[(b.size()-1)-i],0);
        fft(abuf);
        fft(bbuf);
        for (size_t i = 0; i < abuf.size(); ++i)
            abuf[i] = abuf[i]*conj(bbuf[i]);
        fft(abuf,-1);
        for (size_t i = 0; i < c.size(); ++i)
            c[i] = abuf[i].real();
}
using namespace std;

class QueryOfNumberProductSet
{
public:
    void solve(void)
    {
            int L,M,N;
            cin>>L>>M>>N;

            //
            // f(x) = ∑ x^A[i]
            // g(x) = ∑ x^(N-B[i])  (次数がN-B[i]なのは畳み込み後の次数に A[i]-B[i] を入れたいから)
            //
            // とするとき
            //
            // (f*g)(x) = ∑∑ a[i]b[j] x^(A[i]-B[j]+N)
            //          = ∑ c[i] x^i
            //
            // c[N+v] = #{(i,j) | (A[i]-B[j]+N == N+v) } となる
            //
            // よって FFT が使える
            //

            vector<double> a(N+1,0);
            vector<double> b(N+1,0);
            vector<double> c(2*(N+1),0);

            REP(i,L)
            {
                int x;
                cin>>x;
                // 次数に対応する係数だけ 1 にする
                a[x] = 1;
            }

            REP(i,M)
            {
                int x;
                cin>>x;
                b[N-x] = 1;
            }

            convolve(a,b,c);

            int Q;
            cin>>Q;
            REP(v,Q)
            {   // round してから cast しないと期待どおりの値にならない
                cout<<(int)round(c[N+v])<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new QueryOfNumberProductSet();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0