QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #436188 | #8782. Schoolgirls | Forever_Young# | WA | 50ms | 19740kb | C++17 | 3.8kb | 2024-06-08 23:34:31 | 2024-06-08 23:34:31 |
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);
int mod = -1;
for(int i = 1; ; i++) {
if(i * n + 1 >= 10000 && f[i * n + 1]) {
mod = i * n + 1;
break;
}
}
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 pr = findpr(mod);
int cc = 0;
// printf("%d %d\n", pr, mod);
for(int i = 1; i <= mod - 1; i++) {
if(__gcd(i, mod - 1) > 1) {
continue;
}
cc++;
if(cc == 11) {
break;
}
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");
}
}
详细
Test #1:
score: 100
Accepted
time: 34ms
memory: 17644kb
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: 37ms
memory: 17476kb
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: 50ms
memory: 19740kb
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]