QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746478#9631. Median ReplacementNightskyWA 2ms3700kbC++143.1kb2024-11-14 14:46:302024-11-14 14:46:30

Judging History

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

  • [2024-11-14 14:46:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3700kb
  • [2024-11-14 14:46:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;

inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f? -x : x;
}

const int MAXN = 300;
const int Mod = 1e9+7;
int l[MAXN + 10], r[MAXN + 10];
int DP(int n, int x) {
    static int dp[MAXN + 10][2][2];
    dp[0][0][0] = 1;
    int res = 1;
    for (int i = 1; i <= n; ++i) {
        int p1 = x - l[i], p2 = r[i] - x + 1;
        p1 = max(p1, 0ll); p1 = min(p1, r[i] - l[i] + 1);
        p2 = max(p2, 0ll); p2 = min(p2, r[i] - l[i] + 1);
        res = 1ll * res * (r[i] - l[i] + 1) % Mod;
        dp[i][0][0] = 1ll * (dp[i - 1][1][0] + dp[i - 1][0][0]) * p1 % Mod;
        dp[i][1][0] = 1ll * dp[i - 1][0][1] * p1 % Mod;
        dp[i][0][1] = 1ll * dp[i - 1][0][0] * p2 % Mod;
    }
    int sum = ((dp[n][0][0] + dp[n][0][1]) % Mod + dp[n][1][0]) % Mod;
    //assert(res >= sum);
    return (res - sum + Mod) % Mod;
}

inline int fastpow(int x, int p) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = 1ll * ans * x % Mod;
        x = 1ll * x * x % Mod;
        p >>= 1;
    }
    return ans;
}
int Lan(int *X, int *Y, int n, int k) {
    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        int res = 1, prod = 1;
        for (int j = 1; j <= n; ++j)
        {
            if(i == j) continue;
            prod = 1ll * prod * (X[i] - X[j]) % Mod, res = 1ll * res * (k - X[j]) % Mod;
        }
            
        
        if(prod < 0) prod += Mod;
        if(res < 0) res += Mod;
        prod = fastpow(prod, Mod - 2);
        ans = (ans + 1ll * res * Y[i] % Mod * prod ) % Mod;
    }
    if (ans < 0) ans += Mod;
    return ans;
}
signed main() {
    // freopen ("std.in", "r", stdin);
    // freopen ("std.out", "w", stdout);
    int T = read();
    while (T--) {
        int n = read();
        for (int i = 1; i <= n; ++i) l[i] = read();
        for (int i = 1; i <= n; ++i) r[i] = read();

        static int b[MAXN + 10], tot = 0;
        for (int i = 1; i <= n; ++i) b[++tot] = l[i];
        for (int i = 1; i <= n; ++i) b[++tot] = r[i] + 1;
        b[++tot] = 1;
        sort(b + 1, b + tot + 1);
        tot = unique(b + 1, b + tot + 1) - b - 1;
        int ans = 0;
        for (int i = 1; i < tot; ++i) {
            int L = b[i], R = b[i + 1] - 1;
            int len = min(R - L + 1, n + 2);
            static int X[MAXN + 10], Y[MAXN + 10];
            for (int j = 1; j <= len; ++j) {
                X[j] = L + j - 1;
                Y[j] = DP(n, X[j]);
            }
            for (int j = 2; j <= len; ++j) 
                Y[j] = (Y[j - 1] + Y[j]) % Mod;
            if (len == R - L + 1) {
                ans = (ans + Y[len]) % Mod;
            }
            else {
                ans = (ans + Lan(X, Y, len, R)) % Mod;
                ans = (ans + Mod) % Mod;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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: 1ms
memory: 3624kb

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

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
991535207
997019207
997989587
997260335
997366607
997702727
990119687
990774407
991778991

result:

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