QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755033 | #9530. A Game On Tree | ANIG# | WA | 0ms | 3644kb | C++14 | 1.7kb | 2024-11-16 16:17:45 | 2024-11-16 16:17:45 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, mod = 1e9+7;
int n, m, x[N], v[N], lt[N], a[N], b[N], f[N], ni;
struct frac {
int p, q;
friend bool operator < (const frac & a, const frac & b) {
return a.p*b.q < b.p*a.q;
}
};
struct node {
frac t; int id;
}s[N*N];
inline bool cmp (node x, node y) {
if (x.t < y.t) return 1;
if (y.t < x.t) return 0;
return x.id < y.id;
}
int qpow (int x, int y = mod-2) {
int res = 1;
while (y) {
if (y&1) res = res*x%mod;
x = x*x%mod; y >>= 1;
}
return res;
}
int g[N];
void add (int x) {
int sx = 0, bi = qpow(b[x]);
for (int i = 0;i <= n;i++) {
(sx = f[i]-sx) %= mod;
g[i] = sx*bi%mod;
sx = g[i]*a[x]%mod;
}
(a[x] += ni) %= mod; (b[x] -= ni) %= mod;
for (int i = 0;i <= n;i++) {
f[i] = b[x]*g[i]%mod;
if (i) (f[i] += a[x]*g[i-1]) %= mod;
}
}
signed main () {
cin >> n >> m; ni = qpow(n);
for (int i = 1;i <= n;i++) cin >> x[i];
sort(x+1, x+1+n);
for (int i = 1;i <= m;i++) cin >> v[i];
int st = 0;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
s[++st] = (node){-x[i], v[j], j};
}
}
sort(s+1, s+1+st, cmp);
for (int i = 1;i <= m;i++) lt[i] = 1;
for (int i = 1;i <= m;i++) a[i] = 0, b[i] = 1;
f[0] = 1;
int ans = 0;
for (int i = 1;i <= st;i++) {
for (int j = 1;j <= m;j++) {
while (lt[j] <= n && cmp((node){-x[lt[j]], v[j], j}, s[i])) {
add(j);
lt[j]++;
}
(ans += f[m/2]) %= mod;
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
2 3 1 2 2 3 5 1 2 1 5 3 2 4 2
output:
result:
wrong answer 1st lines differ - expected: '443664158', found: ''