Language: C++

#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;
/*
?????????????????¨?????? FFT ???????????????
n?¬??????????g(x) = \sum_{i=0}^n a_i x^i , h(x) = \sum_{i=0}^n b_i x^i ???????????????
f(x) = (g*h)(x) = \sum_{k=0}^{2n} \sum_{i=0}^{k} a_i b_{k-i} x^k
???O(n log n)??§?±??????????

?????????:
g(x)????????°??? vector<T> g
h(x)????????°??? vector<T> h
??¨????????¨???
f = multiply(g, h);
??§f(x)????????°vector<T> f????±??????????

verified by: http://atc001.contest.atcoder.jp/tasks/fft_c
(AtCoder Typical Contest 001 C)

complex, vector, algorithm ?????????????????????????????????????????????
*/
#include<complex>
#include<vector>
#include<algorithm>
using namespace std;
const double PI = 3.141592653589793;
/*
*
 * n?¬??????????f????????????????????¨????????????
 * is_inv = false => ?????????
 * is_inv = true  => ?????????
 * ?????????????????¨??????multiply????????§n??§?????£?????????
 */
using comp=complex<ld>;
void fft(vector<comp> &f, int n, bool is_inv) {
	if (n == 1) return;
	if (n == 2) {
		comp zeta = comp(-1,0);
		comp pow_zeta = 1.0;

		comp f0(f[0]);
		comp f1(f[1]);

		f[0]=f0+1.0*f1;
		f[1]=f0-1.0*f1;
		return;
	}
	vector<comp> f0(n / 2), f1(n / 2);
	for (int i = 0; i < n / 2; i++) {
		f0[i] = f[2 * i];
		f1[i] = f[2 * i + 1];
	
	}
	fft(f0, n / 2, is_inv);
	fft(f1, n / 2, is_inv);
	comp zeta = comp(cos(2 * PI / n), sin(2 * PI / n));
	if (is_inv) zeta = 1.0 / zeta;
	comp pow_zeta = 1.0;
	for (int i = 0; i < n; i++) {
		f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
		pow_zeta *= zeta;
	}
}

template<typename T>
vector<T> multiply(vector<T> &g, vector<T>& h) {
	int n = 1;
	int gs = g.size();
	int hs = h.size();
	int fs = gs + hs - 1;
	while (n <= fs + 1) n *= 2;
	vector<comp> gg(n), hh(n), ff(n);
	for (int i = 0; i < n; i++) {
		gg[i] = (i < gs) ? g[i] : 0;
		hh[i] = (i < hs) ? h[i] : 0;
	}
	fft(gg, n, false);
	fft(hh, n, false);
	for (int i = 0; i < n; i++) ff[i] = gg[i] * hh[i];
	fft(ff, n, true);
	
	vector<T> f(fs);
	for (int i = 0; i < fs; i++) {
		f[i] = (T)round(ff[i].real() / n);
	}
	
	return f;
	
}
const int asize = 2e5+1;
vector<long long int> get_mp(const vector<int>v) {
	vector<long long int>sums(v.size()+1);
	for (int i = 0; i < v.size(); ++i) {
		sums[i+1]=sums[i]+v[i];
	}

	vector<long long int>a(asize);
	vector<long long int>b(asize);
	for (auto sum : sums) {
		a[sum]++;
		b[asize-sum-1]++;
	}
	vector<long long int> c=multiply(a,b);
	vector<long long int>ans(asize);
	for (int i = asize; i < 2 * asize-1; ++i) {
		if (c[i]) {
			ans[i - asize+1] += c[i];
		}
	}
	return ans;
}
vector<long long int>solve(vector<long long int>a, vector<long long int>b) {
	reverse(a.begin(),a.end());

	vector<long long >c=multiply<long long int>(a,b);
	vector<long long int>ans(asize);
	ans[0]=c[asize-1];
	for (int i = 1; i < asize; ++i) {
		ans[i]=c[asize-1-i]+c[asize-1+i];
	}
	return ans; 
}

int main() {
	int N,M,Q;cin>>N>>M>>Q;
	vector<int>as(N),bs(M);
	for (int i = 0; i < N; ++i) {
		cin>>as[i];
	}
	for (int i = 0; i < M; ++i) {
		cin>>bs[i];
	}
	long long int aaa=static_cast<long long int>(N)*(N+1)/2;
	long long int bbb=static_cast<long long int>(M)*(M+1)/2;
	auto a_mp(get_mp(as));
	assert(aaa=accumulate(a_mp.begin(),a_mp.end(),0ll));
	auto b_mp(get_mp(bs));
	assert(bbb = accumulate(b_mp.begin(), b_mp.end(), 0ll));
	auto ans(solve(a_mp,b_mp));
	assert(aaa*bbb==accumulate(ans.begin(),ans.end(),0ll));
	while (Q--) {
		int n;cin>>n;
		cout<<ans[n]<<endl;
	}
	return 0;
}

Compiler output:
a.cc: In function 'void fft(std::vector<std::complex<long double> >&, int, bool)':
a.cc:48:28: error: no match for 'operator*' (operand types are 'double' and 'comp' {aka 'std::complex<long double>'})
   48 |                 f[0]=f0+1.0*f1;
      |                         ~~~^~~
      |                         |   |
      |                         |   comp {aka std::complex<long double>}
      |                         double
In file included from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127,
                 from a.cc:1:
/usr/include/c++/14/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const complex<_Tp>&)'
  400 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:400:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::complex<_Tp>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const _Tp&)'
  409 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:409:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::complex<_Tp>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/complex:418:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const complex<_Tp>&)'
  418 |     operator*(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:418:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   deduced conflicting types for parameter '_Tp' ('double' and 'long double')
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
In file included from /usr/include/c++/14/valarray:605,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:166:
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, struct std::__multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, struct std::__multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, struct std::__multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   'comp' {aka 'std::complex<long double>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, struct std::__multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, struct std::__multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   'comp' {aka 'std::complex<long double>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/valarray:1198:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const valarray<_Tp>&, const valarray<_Tp>&)'
 1198 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/valarray:1198:1: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::valarray<_Tp>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/valarray:1198:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const valarray<_Tp>&, const typename valarray<_Tp>::value_type&)'
 1198 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/valarray:1198:1: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   mismatched types 'const std::valarray<_Tp>' and 'double'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
/usr/include/c++/14/valarray:1198:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const typename valarray<_Tp>::value_type&, const valarray<_Tp>&)'
 1198 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/valarray:1198:1: note:   template argument deduction/substitution failed:
a.cc:48:29: note:   'comp' {aka 'std::complex<long double>'} is not derived from 'const std::valarray<_Tp>'
   48 |                 f[0]=f0+1.0*f1;
      |                             ^~
a.cc:49:28: error: no match for 'operator*' (operand types are 'double' and 'comp' {aka 'std::complex<long double>'})
   49 |                 f[1]=f0-1.0*f1;
      |                         ~~~^~~
      |                         |   |
      |                         |   comp {aka std::complex<long double>}
      |                         double
/usr/include/c++/14/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const complex<_Tp>&)'
  400 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:400:5: note:   template argument deduction/substitution failed:
a.cc:49:29: note:   mismatched types 'const std::complex<_Tp>' and 'double'
   49 |                 f[1]=f0-1.0*f1;
      |                             ^~
/usr/include/c++/14/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const _Tp&)'
  409 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:409:5: note:   template argument deduction/substitution failed:
a.cc:49:29: note:   mismatched types 'const std::complex<_Tp>' and 'double'
   49 |                 f[1]=f0-1.0*f1;
      |                             ^~
/usr/include/c++/14/complex:418:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const complex<_Tp>&)'
  418 |     operator*(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:418:5: note:   template argument deduction/substitution failed:
a.cc:49:29: note:   deduced conflicting types for parameter '_Tp' ('double' and 'long double')
   49 |                 f[1]=f0-1.0*f1;
      |                             ^~
/usr/include/c++/14/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const _Expr<_Dom1, typename _Dom