No.206 数の積集合を求めるクエリ

A[i],B[i] の上限が高々 10^5 であることに着目して解く。
以下は他の人のコードを参考にして解いた。bitset 使うとこんなに簡単に書けるとは..。すげー。

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

            // A[i],B[i] の上限が高々 10^5 であること
            // A,B にて同じ数字が存在しないこと
            // から A,B を bitset で扱うと A & B の計算、 B の一律加算が簡単に表現できる
            bitset<100001> A;
            bitset<100001> B;

            REP(i,L)
            {
                int x;
                cin>>x;
                A.set(x);
            }
            REP(i,M)
            {
                int x;
                cin>>x;
                B.set(x);
            }

            int Q;
            cin>>Q;

            // O(Q*N/64)
            REP(v,Q)
            {
                // 加算によってビットが左にずれる
                cout<<(A & (B<<v)).count()<<endl;
            }
    }
};

fft をつかった O(N*log(N)+Q) 解法がステキ
とはいえフーリエ変換についてはライブラリのを貼り付けただけなんで、ちゃんと勉強しないと..。

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;
            }
    }
};