QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462331#8833. Equalizer Ehrmantrautucup-team2307#AC ✓153ms34920kbC++201.6kb2024-07-03 17:29:022024-07-03 17:29:05

Judging History

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

  • [2024-07-03 17:29:05]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:34920kb
  • [2024-07-03 17:29:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
#define int ll

const int mod = 998244353;

int bpow(int a, int b)
{
    int r = 1;
    while (b > 0)
    {
        if (b%2 == 1)
            r = r*a%mod;
        a = a*a%mod;
        b /= 2;
    }
    return r;
}

int inv(int x)
{
    return bpow(x, mod-2);
}

const int N = 2e6+100;
int f[N];
int rf[N];

int cnk(int n, int k)
{
    return f[n] * rf[k] % mod * rf[n-k] % mod;
}

int dp[1000][1000];

int func(int n, int m)
{
    int ans = bpow(m, n);
    for (int m1=1; m1<=m; m1++)
    {
        int x = m-m1;
        int y = m1;
        ans += 2*bpow(x+y, n);
        ans -= 2*bpow(m1, n);
        ans %= mod;
        ans += mod;
        ans %= mod;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    f[0] = rf[0] = 1;
    for (int i=1; i<N; i++)
        f[i] = i*f[i-1]%mod;
    rf[N-1] = inv(f[N-1]);
    for (int i=N-2; i>=0; i--)
        rf[i] = rf[i+1]*(i+1)%mod;

//    for (int i=1; i<=100; i++)
//        for (int j=1; j<=100; j++)
//    {
//        int s = 2*bpow(j, i)-1;
//        for (int k=0; k<=i-1; k++)
//            s += cnk(i, k) * dp[i-k][j-1], s %= mod;
//        dp[i][j] = s%mod;
//    }
//
//    for (int i=1; i<=10; i++, cout<<"\n")
//        for (int j=1; j<=10; j++)
//            cout<<dp[i][j]<<" ";
//    return 0;

//    while (true)
    {
        int n, m;
        cin>>n>>m;
        cout<<func(n, m)<<endl;
    }

}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 34740kb

input:

1 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 16ms
memory: 34824kb

input:

2 2

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 16ms
memory: 34792kb

input:

69 42

output:

608932821

result:

ok 1 number(s): "608932821"

Test #4:

score: 0
Accepted
time: 16ms
memory: 34796kb

input:

102 156

output:

748401290

result:

ok 1 number(s): "748401290"

Test #5:

score: 0
Accepted
time: 29ms
memory: 34800kb

input:

4646 95641

output:

89806680

result:

ok 1 number(s): "89806680"

Test #6:

score: 0
Accepted
time: 32ms
memory: 34796kb

input:

42849 215151

output:

242217237

result:

ok 1 number(s): "242217237"

Test #7:

score: 0
Accepted
time: 117ms
memory: 34912kb

input:

786416 794116

output:

472898000

result:

ok 1 number(s): "472898000"

Test #8:

score: 0
Accepted
time: 116ms
memory: 34920kb

input:

963852 789456

output:

353211048

result:

ok 1 number(s): "353211048"

Test #9:

score: 0
Accepted
time: 71ms
memory: 34792kb

input:

696969 424242

output:

787990158

result:

ok 1 number(s): "787990158"

Test #10:

score: 0
Accepted
time: 33ms
memory: 34808kb

input:

1000000 123456

output:

533491028

result:

ok 1 number(s): "533491028"

Test #11:

score: 0
Accepted
time: 153ms
memory: 34836kb

input:

1000000 1000000

output:

572586375

result:

ok 1 number(s): "572586375"

Test #12:

score: 0
Accepted
time: 115ms
memory: 34804kb

input:

123456 1000000

output:

486967129

result:

ok 1 number(s): "486967129"

Test #13:

score: 0
Accepted
time: 21ms
memory: 34736kb

input:

789456 1

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 25ms
memory: 34916kb

input:

852516 2

output:

148946358

result:

ok 1 number(s): "148946358"

Test #15:

score: 0
Accepted
time: 24ms
memory: 34732kb

input:

1 953646

output:

40087733

result:

ok 1 number(s): "40087733"

Test #16:

score: 0
Accepted
time: 7ms
memory: 34836kb

input:

3 7686

output:

278212472

result:

ok 1 number(s): "278212472"

Extra Test:

score: 0
Extra Test Passed