QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#466701 | #8833. Equalizer Ehrmantraut | USP_USP_USP# | AC ✓ | 177ms | 18744kb | C++20 | 2.1kb | 2024-07-08 03:06:05 | 2024-07-08 03:06:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define pb push_back
#define all(v) (v).begin(), (v).end()
void dbg_out() { cerr << endl; }
template<typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
template<int MOD>
struct mint {
int x;
mint(): x(0){}
mint(int _x): x(_x%MOD < 0 ? _x%MOD + MOD : _x%MOD) {}
mint& operator+=(mint rhs) { x += rhs.x; if( x >= MOD ) x -= MOD; return *this; }
mint& operator-=(mint rhs) { x -= rhs.x; if( x < 0 ) x += MOD; return *this; }
mint& operator*=(mint rhs) { x = x * rhs.x % MOD; return *this; }
mint& operator/=(mint rhs) { return *this *= rhs.inv(); }
mint operator+(mint rhs) { mint m = *this; return m += rhs; }
mint operator-(mint rhs) { mint m = *this; return m -= rhs; }
mint operator*(mint rhs) { mint m = *this; return m *= rhs; }
mint operator/(mint rhs) { mint m = *this; return m /= rhs; }
mint inv() { return this->pow(MOD-2); }
mint pow(int e) {
mint ret = 1;
for(mint p = *this; e > 0; e /= 2, p *= p) if(e & 1)
ret *= p;
return ret;
}
};
using Z = mint<998244353>;
void solve() {
int n,m;
cin >> n >> m;
Z ans = 0;
vector<Z> fat(n+1), invfat(n+1);
fat[0] = fat[1] = invfat[0] = invfat[1] = Z(1);
for(int i = 2; i <= n; i++){
fat[i] = fat[i-1]*Z(i);
invfat[i] = invfat[i-1]/Z(i);
}
Z x = Z(m).pow(n);
for(int i = 1; i < m; i++){
Z at = x - Z(i).pow(n);
ans += at;
}
/*
for(int i = 1; i < m; i++){
for(int j = 1; j <= n; j++){
Z at = ( Z(m-i).pow(j))*( Z(i).pow(n-j));
at *= fat[n];
at *= invfat[j];
at *= invfat[n-j];
ans += at;
}
}
*/
ans *= Z(2);
/*
for(int i = 1; i < m; i++){
Z r = m-i;
r /= Z(i);
Z pw = r.pow(n+1);
Z num = Z(1) - Z(pw);
Z den = Z(1) - Z(r);
Z end = num/den;
end -= Z(1);
dbg(end.x);
end *= Z(i).pow(n);
dbg(end.x);
ans += end;
}
ans *= Z(2);
*/
Z eq = Z(m).pow(n);
ans += eq;
cout << ans.x << '\n';
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
solve();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
1 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
2 2
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
69 42
output:
608932821
result:
ok 1 number(s): "608932821"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
102 156
output:
748401290
result:
ok 1 number(s): "748401290"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
4646 95641
output:
89806680
result:
ok 1 number(s): "89806680"
Test #6:
score: 0
Accepted
time: 15ms
memory: 3800kb
input:
42849 215151
output:
242217237
result:
ok 1 number(s): "242217237"
Test #7:
score: 0
Accepted
time: 138ms
memory: 15504kb
input:
786416 794116
output:
472898000
result:
ok 1 number(s): "472898000"
Test #8:
score: 0
Accepted
time: 157ms
memory: 18388kb
input:
963852 789456
output:
353211048
result:
ok 1 number(s): "353211048"
Test #9:
score: 0
Accepted
time: 103ms
memory: 13924kb
input:
696969 424242
output:
787990158
result:
ok 1 number(s): "787990158"
Test #10:
score: 0
Accepted
time: 116ms
memory: 18716kb
input:
1000000 123456
output:
533491028
result:
ok 1 number(s): "533491028"
Test #11:
score: 0
Accepted
time: 177ms
memory: 18744kb
input:
1000000 1000000
output:
572586375
result:
ok 1 number(s): "572586375"
Test #12:
score: 0
Accepted
time: 64ms
memory: 5208kb
input:
123456 1000000
output:
486967129
result:
ok 1 number(s): "486967129"
Test #13:
score: 0
Accepted
time: 88ms
memory: 15560kb
input:
789456 1
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 96ms
memory: 16432kb
input:
852516 2
output:
148946358
result:
ok 1 number(s): "148946358"
Test #15:
score: 0
Accepted
time: 4ms
memory: 3540kb
input:
1 953646
output:
40087733
result:
ok 1 number(s): "40087733"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 7686
output:
278212472
result:
ok 1 number(s): "278212472"
Extra Test:
score: 0
Extra Test Passed