QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#808146#9631. Median ReplacementwangjunruiWA 2ms3740kbC++142.2kb2024-12-10 17:24:262024-12-10 17:24:26

Judging History

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

  • [2024-12-10 17:24:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3740kb
  • [2024-12-10 17:24:26]
  • 提交

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) % mod;
	suf[m + 1] = 1;
	for (int i = m; i >= 1; --i)
		suf[i] = suf[i + 1] * (x - i) % mod;
	ll res = 0;
	for (int i = 1; i <= m; ++i)
		(res += Y[i] * (pre[i - 1] * suf[i + 1] % mod) % mod * (((m - i) & 1 ? -1 : 1) * ifac[i - 1] * ifac[m - 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) % mod + (dp[i - 1][0] + dp[i - 1][1]) * x % mod) % 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];
	}
	p[++tot] = 1;
	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 + mod) % mod << '\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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

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: 3684kb

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: 3580kb

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: 0
Accepted
time: 1ms
memory: 3700kb

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:

157838571
539867046
711272106
123881231
497944943
9791579
539012259
963879245
315607794
495624077

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

10
5
462008700 417744555 925098328 70231697 547596413
462008735 417744555 925098328 70231697 547596413
5
294230630 403894618 294230635 403894620 403894617
294230638 403894620 294230635 403894620 403894617
5
757647830 757647826 757647828 184694646 161891480
757647839 757647827 757647830 184694646 161...

output:

713470735
905154643
458869425
477055327
633375786
349097981
980046476
478461437
573246310
810688575

result:

ok 10 lines

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 3696kb

input:

10
150
7 1 8 8 2 3 8 2 1 3 2 10 9 7 3 9 4 5 4 5 10 7 9 9 9 3 4 7 10 8 5 3 5 1 8 4 1 2 7 9 10 9 1 7 4 7 6 8 7 6 6 7 4 5 10 8 7 10 2 8 1 4 9 2 9 3 9 6 2 2 7 7 10 8 4 10 4 1 7 3 3 5 4 3 9 7 4 1 8 1 4 4 2 7 5 4 9 6 5 8 6 4 8 7 4 6 8 8 2 9 8 3 10 9 2 4 6 10 2 8 9 1 6 6 7 8 8 7 8 8 8 3 4 6 3 8 10 10 10 3 ...

output:

8640
12168000
129187200
127409826
660322457
455326368
791475680
954041909
672499972
705451396

result:

wrong answer 2nd lines differ - expected: '8000', found: '12168000'