QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #436199 | #8782. Schoolgirls | Forever_Young# | WA | 227ms | 19548kb | C++17 | 4.0kb | 2024-06-08 23:37:19 | 2024-06-08 23:37:20 |
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 == 101) {
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");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 34ms
memory: 19548kb
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: 38ms
memory: 19540kb
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: 227ms
memory: 19264kb
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]