Submission #924865

#	Time	Username	Problem	Language	Result	Execution time	Memory
924865		junk727	씽크스몰 (kriii3_TT)	C++17	30 / 30	1089 ms	179548 KiB

tt

#include <bits/stdc++.h>
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef complex<double> cpx;
typedef vector<ll> poly;

const double PI = acos(-1);

void FFT(vector<cpx> &a, bool inv)
{
	int n = (int)a.size();

	for(int i=1,j=0;i<n;i++)
	{
		int b=(n>>1);
		while(!((j^=b)&b)) b>>=1;
		if(i<j) swap(a[i],a[j]);
	}

	vector<cpx> roots(n/2);
	double ang = 2*PI/n * (inv?-1:1);

	for(int i=0; i<n/2; i++) roots[i] = cpx(cos(ang * i), sin(ang * i));

	for(int s=1;s<n;s<<=1)
    {
		int step = n/(s<<1);
		for(int i=0; i<n; i+=(s<<1))
			for(int j=0;j<s;j++)
            {
				cpx v=a[s|i|j] * roots[step * j];
				a[s|i|j]=a[i|j]-v;
				a[i|j]+=v;
			}
	}

	if(inv) for(int i=0; i<n; i++) a[i] /= n; 
}

poly multiply(poly &a, poly &b)
{
	int n=2; while(n < a.size()+b.size()) n<<=1;
    vector<cpx> v1(n),v2(n),r1(n),r2(n);
    for(int i=0;i<a.size();i++) v1[i]=cpx(a[i] >> 15, a[i] & 32767);
    for(int i=0;i<b.size();i++) v2[i]=cpx(b[i] >> 15, b[i] & 32767);

    FFT(v1,0); FFT(v2,0);

	for(int i=0;i<n;i++) 	
    {
        int j = (i?(n-i):i);
        cpx ans1 = (v1[i]+conj(v1[j])) * cpx(0.5,0);
        cpx ans2 = (v1[i]-conj(v1[j])) * cpx(0,-0.5);
        cpx ans3 = (v2[i]+conj(v2[j])) * cpx(0.5,0);
        cpx ans4 = (v2[i]-conj(v2[j])) * cpx(0,-0.5);
        r1[i] = (ans1*ans3) + (ans1*ans4)*cpx(0,1);
        r2[i] = (ans2*ans3) + (ans2*ans4)*cpx(0,1);
    }

    FFT(r1,1); FFT(r2,1);

    poly ret(n);
    for(int i=0;i<n;i++)
    {
        ll av = (ll)round(r1[i].real());
        ll bv = (ll)round(r1[i].imag()) + (ll)round(r2[i].real());
        ll cv = (ll)round(r2[i].imag());
        ret[i] = (av<<30)+(bv<<15)+cv;
    }

    return ret;
}

int main()
{
    fastio;
    int n,m; cin >> n >> m; n+=1,m+=1;
    poly a(n),b(m);
    while(n--) cin >> a[n];
    while(m--) cin >> b[m];
    poly ret = multiply(a,b);
    ll ans = 0;
    for(auto i : ret) ans^=i;
    cout << ans;
}

Compilation message (stderr)

tt.cpp: In function 'poly multiply(poly&, poly&)':
tt.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  int n=2; while(n < a.size()+b.size()) n<<=1;
      |                 ~~^~~~~~~~~~~~~~~~~~~
tt.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<a.size();i++) v1[i]=cpx(a[i] >> 15, a[i] & 32767);
      |                 ~^~~~~~~~~
tt.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<b.size();i++) v2[i]=cpx(b[i] >> 15, b[i] & 32767);
      |                 ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10