QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466701#8833. Equalizer EhrmantrautUSP_USP_USP#AC ✓177ms18744kbC++202.1kb2024-07-08 03:06:052024-07-08 03:06:05

Judging History

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

  • [2024-07-08 03:06:05]
  • 评测
  • 测评结果:AC
  • 用时:177ms
  • 内存:18744kb
  • [2024-07-08 03:06:05]
  • 提交

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