QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#808097 | #9631. Median Replacement | wangjunrui | WA | 0ms | 3744kb | C++14 | 2.2kb | 2024-12-10 17:03:06 | 2024-12-10 17:03:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 300 + 5;
constexpr int mod = 1e9 + 7;
typedef long long ll;
int n, L[N], R[N];
int p[N], tot;
int m;
ll Y[N];
ll fac[N], ifac[N];
inline ll quickpow(ll a, int b)
{
ll res = 1;
while (b)
{
if (b & 1)
(res *= a) %= mod;
(a *= a) %= mod;
b >>= 1;
}
return res;
}
inline void init(int _n)
{
fac[0] = 1;
for (int i = 1; i <= _n; ++i)
fac[i] = fac[i - 1] * i % mod;
ifac[_n] = quickpow(fac[_n], mod - 2);
for (int i = _n; i >= 1; --i)
ifac[i - 1] = ifac[i] * i % mod;
}
ll pre[N], suf[N];
inline auto lagrange(int x)
{
pre[0] = 1;
for (int i = 1; i <= m; ++i)
pre[i] = pre[i - 1] * (x - i);
suf[m + 1] = 1;
for (int i = m; i >= 1; --i)
suf[i] = suf[i + 1] * (x - i);
ll res = 0;
for (int i = 1; i <= m; ++i)
(res += Y[i] * (pre[i - 1] * suf[i + 1] % mod) % mod * (((n - i) & 1 ? -1 : 1) * ifac[i - 1] * ifac[n - i] % mod)) %= mod;
return res;
}
ll dp[N][4];
inline auto solve(int mid)
{
dp[0][2] = 1;
for (int i = 1; i <= n; ++i)
{
int x = max(R[i] - max(L[i], mid), 0), y = (R[i] - L[i]) - x;
dp[i][0] = dp[i - 1][2] * x % mod;
dp[i][1] = dp[i - 1][0] * y % mod;
dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) * y % mod;
dp[i][3] = (dp[i - 1][3] * (x + y) + (dp[i - 1][0] + dp[i - 1][1]) * x) % mod;
}
return dp[n][3];
}
inline void _main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> L[i];
for (int i = 1; i <= n; ++i)
{
cin >> R[i];
++R[i];
}
for (int i = 1; i <= n; ++i)
{
p[++tot] = L[i];
p[++tot] = R[i];
}
sort(p + 1, p + 1 + tot);
tot = (int)(unique(p + 1, p + 1 + tot) - p - 1);
ll ans = 0;
for (int i = 1; i < tot; ++i)
{
if (p[i + 1] - p[i] > n + 2)
{
m = n + 2;
for (int j = p[i]; j < p[i] + n + 2; ++j)
Y[j - p[i] + 1] = (Y[j - p[i]] + solve(j)) % mod;
(ans += lagrange(p[i + 1] - p[i])) %= mod;
}
else
for (int j = p[i]; j < p[i + 1]; ++j)
(ans += solve(j)) %= mod;
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init(N - 5);
int test = 1;
cin >> test;
while (test--)
_main();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
10 5 5 1 4 3 2 14 2 5 3 2 5 4 5 1 2 3 13 7 1 2 3 5 5 2 5 3 1 10 2 12 3 2 5 5 5 3 1 5 57 5 3 1 5 5 2 2 3 3 5 4 5 4 4 5 5 4 5 3 5 3 13 7 3 5 3 5 5 1 4 2 3 14 3 4 2 3 5 1 2 5 4 5 2 8 5 7 5 5 1 1 3 5 1 8 2 3 8 1 5 4 4 4 2 3 5 10 5 2 3
output:
180 170 650 265 182 173 120 296 192 131
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
10 5 1 2 2 5 3 6 4 2 6 3 5 4 4 1 4 3 6 7 2 5 3 5 5 3 4 2 4 5 7 5 2 6 5 1 5 3 5 2 7 7 3 5 2 5 1 3 3 2 2 10 5 3 2 2 5 4 4 4 5 3 4 11 9 5 3 5 5 3 2 1 3 13 5 2 1 5 5 5 4 1 2 5 10 6 1 2 5 5 3 5 3 4 2 5 9 3 5 2 5 1 1 3 2 1 7 3 3 3 1
output:
120 230 144 110 110 289 324 89 140 122
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 5 3 1 3 4 4 9 1 3 10 4 5 1 1 3 1 1 9 1 3 3 1 5 5 1 2 3 1 74 1 2 3 1 5 2 5 5 3 4 5 6 8 3 4 5 2 1 3 4 5 2 4 6 4 5 5 2 4 2 1 3 2 11 3 2 3 5 1 5 4 4 2 1 14 6 6 2 5 4 1 3 5 1 9 2 4 5 1 5 4 1 2 4 4 6 1 6 4 4 5 3 2 5 3 5 8 8 5 3 5
output:
196 76 140 172 72 80 486 84 65 224
result:
ok 10 lines
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3688kb
input:
10 5 676437428 903889545 700650370 965758082 146716866 676437431 903889567 700650370 965758082 146716866 5 517457740 64600397 388618400 783268973 388618400 517457797 64600397 388618400 783268973 388618400 5 971452763 106948541 259878781 537741075 9504353 971452780 106948544 259878781 537741075 95043...
output:
-880063865 -346349351 -25576073 620554477 769571388 446972342 53907716 -46295545 -26497235 -92322617
result:
wrong answer 1st lines differ - expected: '157838571', found: '-880063865'