QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#436195 | #8782. Schoolgirls | Forever_Young# | WA | 56ms | 18540kb | C++17 | 4.0kb | 2024-06-08 23:36:36 | 2024-06-08 23:36:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
inline LL fastpo(LL x, LL n, LL mod) {
LL res(1);
while(n) {
if(n & 1) {
res = res * (LL)x % mod;
}
x = x * (LL) x % mod;
n /= 2;
}
return res;
}
const int inf = 1e9 + 7;
const int L = 9999999;
const int N = 10000111;
bool f[N];
int np = 0;
int p[N / 10];
const int M = 53333;
int a[M], b[M], c[M], h[M];
bool answer[M];
vector<int> q[M];
int powmod (int a, int b, int p) {
int res = 1;
while (b)
if (b & 1)
res = int (res * 1ll * a % p), --b;
else
a = int (a * 1ll * a % p), b >>= 1;
return res;
}
int findpr (int p) {
vector<int> fact;
int phi = p-1, n = phi;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
fact.push_back (i);
while (n % i == 0)
n /= i;
}
if (n > 1)
fact.push_back (n);
for (int res=2; res<=p; ++res) {
bool ok = true;
for (size_t i=0; i<fact.size() && ok; ++i)
ok &= powmod (res, phi / fact[i], p) != 1;
if (ok) return res;
}
return -1;
}
int main() {
fill(f + 2, f + L + 1, true);
p[0] = inf;
for(int i = 2; i <= L; i++) {
if(f[i]) {
p[++np] = i;
}
for(int j = 1; j <= np && p[j] * i <= L && i % p[j - 1]; j++) {
f[i * p[j]] = 0;
}
}
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
for(int i = 1; i <= k; i++) {
int r;
scanf("%d", &r);
for(int j = 0; j < r; j++) {
int x;
scanf("%d", &x);
q[i].pb(x);
}
answer[i] = true;
}
int mod = -1;
int cc = 0;
for(int i = 1; i * n + 1 <= L; i++) {
if(i * n + 1 >= 10000 && f[i * n + 1]) {
mod = i * n + 1;
} else {
continue;
}
cc++;
if(cc == 11) {
break;
}
int pr = findpr(mod);
// printf("%d %d\n", pr, mod);
for(int i = 1; i <= 1; i++) {
int pp = fastpo(pr, i, mod);
int g = fastpo(pp, (mod - 1) / n, mod);
// printf("g = %d %d\n", g, fastpo(g, n, mod));
for(int i = 1; i <= n; i++) {
h[i] = i == 1 ? 1 : (LL)h[i - 1] * g % mod;
}
for(int j = 1; j <= m; j++) {
h[n + j] = ((LL)h[c[j]] + h[a[j]] - h[b[j]] + mod) % mod;
}
// for(int i = 1; i <= n + m; i++) {
// printf("%d ", h[i]);
// }
// printf("\n");
for(int j = 1; j <= k; j++) {
int r = q[j].size();
set<int> st;
int sum = 0;
vector<int> xs;
// printf("j = %d\n", j);
for(int id : q[j]) {
int x = h[id];
xs.pb(x);
sum = (sum + x) % mod;
// if(j == 3) {
// printf("%d %d %d\n", id, x, int((LL)x * g % mod));
// }
}
sum = (LL)sum * fastpo(r, mod - 2, mod) % mod;
for(int x : xs) {
st.insert((x - sum + mod) % mod);
}
bool flag = true;
for(int x : xs) {
int y = (LL)(x - sum + mod) * g % mod;
if(st.count(y) == 0) {
flag = false;
break;
}
}
if(!flag) {
answer[j] = false;
}
}
}
}
for(int i = 1; i <= k; i++) {
printf("%s\n", answer[i] ? "Yes" : "No");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 42ms
memory: 17824kb
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: 34ms
memory: 18492kb
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: 56ms
memory: 18540kb
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 No No No No No No No No No No Yes No No No No No No Yes No Yes No No No No No No No No No No No No Yes No No No No No No No No Yes No No No No No Yes No Yes No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No Yes No No No No No N...
result:
wrong answer expected NO, found YES [108th token]