QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#254140#3840. Pass the Ball!surenjamtsCompile Error//C++143.5kb2023-11-18 01:50:072023-11-18 01:50:08

Judging History

This is the latest submission verdict.

  • [2023-11-18 01:50:08]
  • Judged
  • [2023-11-18 01:50:07]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define S second
#define F first
#define PI 3.14159265358979323846;

typedef complex<long double> Complex;

void fft( vector<Complex> &a, bool inverse = false) {
    ll n = a.size();

    if (n <= 1) {
        return;
    }

    // Divide
    vector<Complex> a0(n / 2), a1(n / 2);

    for (int i = 0, j = 0; i < n; i += 2, ++j) {
        a0[j] = a[i];
        a1[j] = a[i + 1];
    }

    // Recursively compute FFT on both halves
    fft(a0, inverse);
    fft(a1, inverse);

    // Combine
    long double angle = (inverse ? 2.0 : -2.0) * PI / n;
    Complex w(1), wn(std::cos(angle), std::sin(angle));

    for (ll i = 0; i < n / 2; ++i) {
        Complex t = w * a1[i];
        a[i] = a0[i] + t;
        a[i + n / 2] = a0[i] - t;
        w *= wn;
    }

    if (inverse) {
        for (ll i = 0; i < n; ++i) {
            a[i] /= 2;
        }
    }
}

vector<ll> multiplyPolynomials(const vector<ll> &poly1, const vector<ll> &poly2) {
	ll n = 1;
    while (n < poly1.size() + poly2.size() - 1) {
        n <<= 1;
    }

    vector<Complex> a(n), b(n);

    // Initialize coefficients
    for (ll i = 0; i < poly1.size(); ++i) {
        a[i] = poly1[i];
    }

    for (ll i = 0; i < poly2.size(); ++i) {
        b[i] = poly2[i];
    }

    // FFT for both polynomials
    fft(a);
    fft(b);

    // Pointwise multiplication
    for (ll i = 0; i < n; ++i) {
        a[i] *= b[i];
    }

    // Inverse FFT to get the result
    fft(a, true);

    // Extract integer coefficients from the complex numbers
    vector<ll> result(n);
    for (ll i = 0; i < n; ++i) {
        result[i] = static_cast<ll>(round(a[i].real()));
    }

    return result;
}

ll child[100045];
bool vis[100045];
vector < ll > vc[100045];
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
    ll n, q, e;
    cin >> n >> q;
    for(ll i = 1; i <= n; i ++ ){
        cin >> e;
        child[i] = e;
    }
    ll l = 0;
    for(ll i = 1; i <= n; i ++ ){
        if( vis[ i ] == 0 ){
            vis[ i ] = 1;
            ll p = i;
            l ++;
            while( child[p] != i ){
                vis[ child[p] ] = 1;
                vc[l].pb( child[p] );
                p = child[p];
                if( child[p] == i ){
                    vc[l].pb( child[p] );
                }
            }
        }
    }
    vector < ll > poly2; 
    vector < vector< ll > > hair;
    vector < vector< ll > > VC[100045];
	map < ll, ll > mp;
	map < ll, ll > ::iterator it; 
	for(ll i = 1; i <= l; i ++ ){
    	for(ll j = vc[i].size()-1; j >= 0; j --  ){
    		poly2.pb( vc[i][j] );
		}
		for(ll j = vc[i].size()-1; j >= 0; j --  ){
    		poly2.pb( vc[i][j] );
		}
    	vector<ll> result = multiplyPolynomials(vc[i], poly2);
    	vector< ll > d;
    	for(ll k = 2*vc[i].size()-1; k >= vc[i].size(); k -- ){
			d.pb( result[k] ); 
		}
		VC[d.size()].pb( d );
    	mp[ d.size() ] = 1;
    	d.clear();
    	result.clear();
    	poly2.clear();
	}
	for( it = mp.begin(); it != mp.end(); it ++ ){
		ll s = it->F;
		vector < ll > v(s);
		for(ll i = 0; i < VC[s].size(); i ++ ){
			for(ll j = 0; j < VC[s][i].size(); j ++ ){
				v[j] += VC[s][i][j];
			}
		}
		hair.pb( v );
		v.clear();
	}
	ll k;
	while( q -- ){
		cin >> k;
		ll sum = 0;
		for(ll i = 0; i < hair.size(); i ++ ){
			ll c = hair[i].size();
			sum += hair[i][k % c];
		}
		cout << sum << "\n";
	}
}

詳細信息

answer.code: In function ‘void fft(std::vector<std::complex<long double> >&, bool)’:
answer.code:32:53: error: expected primary-expression before ‘/’ token
   32 |     long double angle = (inverse ? 2.0 : -2.0) * PI / n;
      |                                                     ^