QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444927#8782. Schoolgirlsucup-team1338WA 3ms3644kbC++203.0kb2024-06-15 22:28:112024-06-15 22:28:11

Judging History

你现在查看的是最新测评结果

  • [2024-06-15 22:28:11]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3644kb
  • [2024-06-15 22:28:11]
  • 提交

answer

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int; using i64 = long long; using ui64 = unsigned long long; using i128 = __int128;
const int INF = 1e9; const i64 LLNF = 4e18;

template< class Tp > void chkmax( Tp &x, Tp y ) { x = max( x, y ); }
template< class Tp > void chkmin( Tp &x, Tp y ) { x = min( x, y ); }

int log( int x ) { return 31 - __builtin_clz( x ); }
int log( i64 x ) { return 63 - __builtin_clzll( x ); }

mt19937_64 rng( 19260817 );
i64 rand( i64 L, i64 R ) { return rng( ) % ( R - L + 1 ) + L; }

i64 qpow( i64 a, i64 b, i64 p ) { i64 c = 1; for( ; b; b >>= 1, a = ( i128 ) a * a % p ) if( b & 1 ) c = ( i128 ) c * a % p; return c; }

vector< int > getp( int n ) { vector< int > pn; for( int p = 2; p * p <= n; p ++ ) if( n % p == 0 ) { pn.emplace_back( p ); while( n % p == 0 ) n /= p; } if( n > 1 ) pn.emplace_back( n ); return pn; }

// miller-rabin
bool isp( i64 n ) {
	int a = 0; i64 k = n - 1; while( k % 2 == 0 ) a ++, k /= 2;

	constexpr int tests = 100;
	for( int _ = 1; _ <= tests; _ ++ ) {
		i64 x = rand( 1, n - 1 );
		if( gcd( n, x ) > 1 ) return false;
		i64 y = qpow( x, k, n );
		for( int i = 0; i <= a - 1; i ++ ) {
			if( ( y != 1 && y != n - 1 ) && ( i128 ) y * y % n == 1 ) return false;
			y = ( i128 ) y * y % n;
		}
		if( y != 1 ) return false;
	}
	return true;
}

// return p, where p is any prime mod n = 1.
i64 findp( int n ) {
	i64 M = 1e15; i64 K = M / n;
	while( true ) { i64 p = rand( 1, K ) * n + 1; if( isp( p ) ) return p; }
}

// return g ** ( ( p - 1 ) / n ) mod p, where g is any primitive root.
i64 findg( i64 p, int n ) {
	assert( ( p - 1 ) % n == 0 );
	vector< int > pn = getp( n );
	while( true ) {
		i64 g = rand( 1, p - 1 ); i64 h = qpow( g, ( p - 1 ) / n, p );
		bool good = true; for( int q : pn ) if( qpow( h, n / q, p ) == 1 ) good = false;
		if( good ) return h;
	}
}

void solve( ) {
	int n, m, k; cin >> n >> m >> k; int N = lcm( 2, n ); i64 p = findp( N );

	vector< i64 > z( n + m ); i64 e = findg( p, n );
	for( int i = 0; i < n; i ++ ) z[i] = qpow( e, i, p );
	for( int i = n; i < n + m; i ++ ) { int a, b, c; cin >> a >> b >> c; a --, b --, c --; z[i] = ( z[a] + z[c] - z[b] + p ) % p; }

	while( k -- ) {
		int r; cin >> r; vector< i64 > I( r ); for( int j = 0; j < r; j ++ ) cin >> I[j], I[j] --;
		i64 z0 = 0; for( int i : I ) z0 = ( z0 + z[i] ) % p;
		vector< i64 > y; for( int i : I ) y.emplace_back( ( ( i128 ) r * z[i] % p - z0 + p ) % p ); sort( y.begin( ), y.end( ) );
		if( N % r != 0 ) {
			if( y[0] == y[r - 1] ) cout << "Yes" << "\n";
			else cout << "No" << "\n";
		}
		else {
			i64 f = qpow(e,n/r,p);
			bool good = true; for( i64 x : y ) { i64 fx = ( i128 ) x * f % p; good &= binary_search( y.begin( ), y.end( ), fx ); }
			if( good ) cout << "Yes" << "\n";
			else cout << "No" << "\n";
		}
	}
}

int main( ) {
	ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
	int T = 1; while( T -- ) solve( ); return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

3 6 8
1 2 3
3 1 4
5 4 3
3 1 2
4 5 3
4 5 2
6 4 7 6 5 1 2
3 1 3 2
3 1 1 8
4 2 5 6 7
3 2 1 4
3 6 5 9
3 4 7 9
4 1 3 2 8

output:

Yes
Yes
Yes
No
No
No
Yes
No

result:

ok 8 token(s): yes count is 4, no count is 4

Test #2:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

12 0 1
12 12 11 10 9 8 7 6 5 4 3 2 1

output:

Yes

result:

ok YES

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 3620kb

input:

3 0 6685
5 1 3 1 2 2
3 1 2 3
5 3 1 3 3 1
4 1 1 1 3
3 3 2 1
5 2 3 2 1 3
6 2 2 3 2 3 1
5 3 1 2 3 2
3 3 3 2
5 3 2 2 2 3
5 2 2 3 3 1
6 3 3 1 3 1 3
6 2 3 3 2 2 1
5 2 2 3 2 2
6 2 3 3 2 1 3
6 2 2 2 2 1 3
3 3 1 2
4 3 2 1 1
5 3 1 3 2 3
4 3 1 1 2
4 2 2 2 3
3 1 2 2
4 2 3 3 1
3 2 2 2
4 1 2 2 3
3 3 3 3
4 1 3 1 3...

output:

No
Yes
No
No
Yes
No
Yes
No
No
No
No
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
Yes
No
No
No
No
No
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
No
No
No
No
Ye...

result:

wrong answer expected NO, found YES [7th token]