QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457749#8833. Equalizer Ehrmantrautucup-team052#AC ✓239ms15424kbC++231.8kb2024-06-29 13:53:402024-06-29 13:53:41

Judging History

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

  • [2024-06-29 13:53:41]
  • 评测
  • 测评结果:AC
  • 用时:239ms
  • 内存:15424kb
  • [2024-06-29 13:53:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int add(int x,int y,int z) {return add(add(x,y),z);}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1LL*x*y%mod;}
inline int mul(int x,int y,int z) {return mul(mul(x,y),z);}
#define inc(x,y) x=add(x,y)
#define dec(x,y) x=sub(x,y)
int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=mul(ans,x);
		x=mul(x,x);
		y>>=1;
	}
	return ans;
}
int Inv(int x){return qpow(x,mod-2);}
#define N 1000005
int fac[N],inv[N],ifac[N];
void init()
{
	fac[0]=1; for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
	inv[0]=inv[1]=1; for(int i=2;i<N;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
	ifac[0]=1; for(int i=1;i<N;i++) ifac[i]=mul(ifac[i-1],inv[i]);
}
int C(int x,int y){return x>=y?mul(fac[x],ifac[x-y],ifac[y]):0;}
signed main()
{
	init();
	int n,m; cin>>n>>m;
	int ans=0;
	for(int v=1;v<=m;v++)
	{
		int w0=mul(2,qpow(m,n)),w1=qpow(m-v+1,n);
		ans=add(ans,sub(w0,w1));
	}
	// cout<<ans<<endl;
	// for(int i=0;i<n;i++)
	{
		int i=n;
		int sum=0;
		for(int v=1;v<=m;v++)
		{
			int tw=mul(2,qpow(v,n-i)); tw=sub(tw,1);
			int tx=qpow(m-v,i);
			sum=add(sum,mul(tw,tx));
		}
		ans=sub(ans,mul(sum,C(n,i)));
	}
	cout<<ans<<endl;
	return 0;
}



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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 15352kb

input:

1 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 15ms
memory: 15412kb

input:

2 2

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 11ms
memory: 15212kb

input:

69 42

output:

608932821

result:

ok 1 number(s): "608932821"

Test #4:

score: 0
Accepted
time: 15ms
memory: 15348kb

input:

102 156

output:

748401290

result:

ok 1 number(s): "748401290"

Test #5:

score: 0
Accepted
time: 22ms
memory: 15348kb

input:

4646 95641

output:

89806680

result:

ok 1 number(s): "89806680"

Test #6:

score: 0
Accepted
time: 41ms
memory: 15228kb

input:

42849 215151

output:

242217237

result:

ok 1 number(s): "242217237"

Test #7:

score: 0
Accepted
time: 191ms
memory: 15348kb

input:

786416 794116

output:

472898000

result:

ok 1 number(s): "472898000"

Test #8:

score: 0
Accepted
time: 187ms
memory: 15352kb

input:

963852 789456

output:

353211048

result:

ok 1 number(s): "353211048"

Test #9:

score: 0
Accepted
time: 107ms
memory: 15404kb

input:

696969 424242

output:

787990158

result:

ok 1 number(s): "787990158"

Test #10:

score: 0
Accepted
time: 38ms
memory: 15368kb

input:

1000000 123456

output:

533491028

result:

ok 1 number(s): "533491028"

Test #11:

score: 0
Accepted
time: 239ms
memory: 15356kb

input:

1000000 1000000

output:

572586375

result:

ok 1 number(s): "572586375"

Test #12:

score: 0
Accepted
time: 200ms
memory: 15348kb

input:

123456 1000000

output:

486967129

result:

ok 1 number(s): "486967129"

Test #13:

score: 0
Accepted
time: 11ms
memory: 15424kb

input:

789456 1

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 10ms
memory: 15236kb

input:

852516 2

output:

148946358

result:

ok 1 number(s): "148946358"

Test #15:

score: 0
Accepted
time: 23ms
memory: 15232kb

input:

1 953646

output:

40087733

result:

ok 1 number(s): "40087733"

Test #16:

score: 0
Accepted
time: 14ms
memory: 15360kb

input:

3 7686

output:

278212472

result:

ok 1 number(s): "278212472"

Extra Test:

score: 0
Extra Test Passed