結果

問題 No.206 数の積集合を求めるクエリ
ユーザー karinohitokarinohito
提出日時 2022-09-19 09:12:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 364 ms / 7,000 ms
コード長 4,230 bytes
コンパイル時間 2,318 ms
コンパイル使用メモリ 207,688 KB
実行使用メモリ 12,464 KB
最終ジャッジ日時 2023-08-23 18:47:57
合計ジャッジ時間 8,998 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 6 ms
4,376 KB
testcase_08 AC 6 ms
4,376 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 10 ms
4,376 KB
testcase_13 AC 10 ms
4,380 KB
testcase_14 AC 9 ms
4,376 KB
testcase_15 AC 10 ms
4,380 KB
testcase_16 AC 10 ms
4,376 KB
testcase_17 AC 231 ms
12,464 KB
testcase_18 AC 223 ms
12,360 KB
testcase_19 AC 232 ms
12,224 KB
testcase_20 AC 229 ms
12,400 KB
testcase_21 AC 227 ms
12,464 KB
testcase_22 AC 226 ms
12,200 KB
testcase_23 AC 234 ms
12,276 KB
testcase_24 AC 364 ms
12,356 KB
testcase_25 AC 358 ms
12,188 KB
testcase_26 AC 350 ms
12,400 KB
testcase_27 AC 314 ms
12,368 KB
testcase_28 AC 353 ms
12,228 KB
testcase_29 AC 356 ms
12,188 KB
testcase_30 AC 359 ms
12,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <complex>
#include <random>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vvvvvll = vector<vvvvll>;
using vvvvvvll = vector<vvvvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvvvb = vector<vvvb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vvvvd = vector<vvvd>;
using vvvvvd = vector<vvvvd>;
#define all(A) A.begin(),A.end()
#define ALL(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
using pqr = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>;
#define tN(t) (t==1?XN:YN)
#define tS(t) (t==1?XS:YS)
#define tA(t) (t==1?XA:YA)

template<class T>
bool chmax(T& p, T q, bool C = 1) {
    if (C == 0 && p == q) {
        return 1;
    }
    if (p < q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}

template<class T>
bool chmin(T& p, T q, bool C = 1) {
    if (C == 0 && p == q) {
        return 1;
    }
    if (p > q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}

ll gcd(ll(a), ll(b)) {
    if (b == 0)return a;
    ll c = a;
    while (a % b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return b;
}

vector<ll> fact, factinv, inv;
ll mod = 998244353;
void prenCkModp(ll n) {
	fact.resize(n + 5);
	factinv.resize(n + 5);
	inv.resize(n + 5);
	fact.at(0) = fact.at(1) = 1;
	factinv.at(0) = factinv.at(1) = 1;
	inv.at(1) = 1;
	for (ll i = 2; i < n + 5; i++) {
		fact.at(i) = (fact.at(i - 1) * i) % mod;
		inv.at(i) = mod - (inv.at(mod % i) * (mod / i)) % mod;
		factinv.at(i) = (factinv.at(i - 1) * inv.at(i)) % mod;
	}

}
ll nCk(ll n, ll k) {
	if (n < k) return 0;
	return fact.at(n) * (factinv.at(k) * factinv.at(n - k) % mod) % mod;
}



/*
ll modPow(long long a, long long n, long long p) {
    if (n == 0) return 1; // 0乗にも対応する場合
    if (n == 1) return a % p;
    if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
    long long t = modPow(a, n / 2, p);
    return (t * t) % p;
}*/


ll modPow(ll a,ll n,ll p){
    ll res=1;
    ll k=a;
    while(n>0){
        if(n%2==1){
            res*=k;
            if(res>p)res%=p;
        }
        k=k*k;
        if(k>p)k%=p;
        n/=2;
    }
    return res;
}

const ll NTTmod=998244353;
ll inva(ll N,ll mod=998244353) {
    return modPow(N,mod-2,mod);
}
void NTT(vector<ll>& V,int inv){
    ll len=V.size();
    if(len==1)return;

    ll m=len;
    ll k=2;
    ll baseb=modPow(3,(NTTmod-1)/len,NTTmod);
    if(inv==-1)baseb=inva(baseb);
    vector<ll> NV(len);
    while(m>1){
        int hm=(m>>1);
        ll a=1,b=3;
        b=modPow(baseb,hm,NTTmod);
        rep(i,hm){
            a=1;
            rep(d,k){
                
                int id=i+hm*d;
                int ide=i+m*d;
                int ido=i+hm+m*d;
                if(ide>=len)ide-=len;
                if(ido>=len)ido-=len;
                ll s=V[ide];
                ll t=a*V[ido]%NTTmod;

                s%=NTTmod;
                NV[id]=(s+t)%NTTmod;
                //NV[(id+m)%len]=(s-t+NTTmod);
                a*=b;
                if(a>NTTmod)a%=NTTmod;
            }
        }
        V=NV;
        m=(m>>1);
        k*=2;
    }
    
}


template<class T>
vector<ll> multiply(vector<T> f,vector<T> g){
    
    int len=1;
    while(len<f.size()+g.size())len*=2;
    vector<ll> cf(len,0),cg(len,0);
    rep(i,f.size())cf[i]=f[i];
    rep(i,g.size())cg[i]=g[i];
    NTT(cf,1);
    NTT(cg,1);
    rep(i,len){
        cf[i]*=cg[i];
        cf[i]%=NTTmod;
    }
    NTT(cf,-1);
    vector<ll> res(len);
    rep(i,len)res[i]=(cf[i]*inva(len))%NTTmod;
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll L,M,N;
    cin>>L>>M>>N;
    vll A(N,0),B(N,0);
    rep(i,L){
        ll a;
        cin>>a;
        A[a-1]++;
    }
    rep(i,M){
        ll b;
        cin>>b;
        b--;
        B[b]++;
    }
    reverse(all(B));
    auto C=multiply(A,B);
    ll Q;
    cin>>Q;
    rep(q,Q){
        cout<<C[N+q-1]<<endl;
    }

}
0