QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462331 | #8833. Equalizer Ehrmantraut | ucup-team2307# | AC ✓ | 153ms | 34920kb | C++20 | 1.6kb | 2024-07-03 17:29:02 | 2024-07-03 17:29:05 |
Judging History
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,我给组数据试试?
详细
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