#include #include #include #include #include using namespace std; using ll = long long int; // Garner のアルゴリズム ( 計算量 O(N^2) ) // x ≡ a_1 (mod m_1), ..., x ≡ a_N (mod m_N) を満たす最小の x を返す // m_1, m_2, ... m_N は相異なる素数である必要がある // x = k_0 + k_1*m_1 + k_2*(m_1*m_2) + ... k_{N-1}*(m_1*m_2* ... *m_{N-1}) として、 // 1 つ目の式から順に操作することで係数 k_i を下から決定していく ll mod_pow(ll X, ll N, ll mod) { ll ret = 1; for(; N>0; N>>=1) { if(N & 1) (ret *= X) %= mod; (X *= X) %= mod; } return ret; } ll garner(vector values, vector mods, ll mod) { assert(values.size() == mods.size()); int N = values.size(); vector coeff(N); for(int i=0; i ntt; とかで十分です template struct NTT { int get_mod() { return mod; } vector dft(vector A, int N, int sgn = 1) { for(int i=0, j=1; j> 1; k>(i ^= k); k >>= 1); if(j < i) swap(A[i], A[j]); } for(int m=2; m<=N; m*=2) { ll zeta = mod_pow(primitive_root, (mod - 1) / m, mod); if(sgn < 0) zeta = mod_pow(zeta, mod - 2, mod); for(int i=0; i= mod) A[u] -= mod; while(A[v] >= mod) A[v] -= mod; zeta_pow = zeta_pow * zeta % mod; } } } return A; } vector inv_dft(vector A, int N) { A = dft(A, N, -1); ll inv_N = mod_pow(N, mod-2, mod); for(int i=0; i multiply(vector A, vector B) { int sz = A.size() + B.size() + 1; int N = 1; while(N < sz) N *= 2; A.resize(N), B.resize(N); A = dft(A, N), B = dft(B, N); vector F(N); for(int i=0; i; using NTT_2 = NTT< 469762049, 3>; using NTT_3 = NTT<1224736769, 3>; vector convolution_using_ntt(vector A, vector B, ll mod) { for(auto &x : A) x %= mod; for(auto &x : B) x %= mod; NTT_1 ntt_1; NTT_2 ntt_2; NTT_3 ntt_3; vector< vector > convo(3); convo[0] = ntt_1.multiply(A, B); convo[1] = ntt_2.multiply(A, B); convo[2] = ntt_3.multiply(A, B); int N = convo[0].size(); vector ret(N), mods(3); mods[0] = ntt_1.get_mod(); mods[1] = ntt_2.get_mod(); mods[2] = ntt_3.get_mod(); for(int i=0; i values(3); for(int k=0; k<3; k++) { values[k] = convo[k][i]; } ret[i] = garner(values, mods, mod); } return ret; } int main() { int L, M, N; cin >> L >> M >> N; vector X(N), Y(N); for(int i=0; i> val; val--; X[val]++; } for(int i=0; i> val; Y[N - val]++; } vector ans = convolution_using_ntt(X, Y, 1LL << 60); int Q; cin >> Q; for(int i=0; i