QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#808097#9631. Median ReplacementwangjunruiWA 0ms3744kbC++142.2kb2024-12-10 17:03:062024-12-10 17:03:07

Judging History

你现在查看的是最新测评结果

  • [2024-12-10 17:03:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3744kb
  • [2024-12-10 17:03:06]
  • 提交

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'