oj.uz

Submission #924865

# Submission time Handle Problem Language Result Execution time Memory
924865 2024-02-10T00:55:39 Z junk727 씽크스몰 (kriii3_TT) C++17
30 / 30
 1089 ms 179548 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2908 KB Output is correct
2 Correct 35 ms 10588 KB Output is correct
3 Correct 39 ms 10976 KB Output is correct
4 Correct 78 ms 20768 KB Output is correct
5 Correct 74 ms 21068 KB Output is correct
6 Correct 71 ms 20824 KB Output is correct
7 Correct 79 ms 21080 KB Output is correct
8 Correct 81 ms 21288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 42060 KB Output is correct
2 Correct 355 ms 82428 KB Output is correct
3 Correct 386 ms 84048 KB Output is correct
4 Correct 1012 ms 172724 KB Output is correct
5 Correct 1002 ms 169796 KB Output is correct
6 Correct 1018 ms 175556 KB Output is correct
7 Correct 1089 ms 179548 KB Output is correct
8 Correct 1006 ms 177904 KB Output is correct