UOJ Logo Universal Online Judge

UOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#621184#424. 【集训队作业2018】countCry_For_theMoon100117ms8108kbC++ 141.6kb2023-05-03 10:47:552023-05-03 10:47:57

测评历史

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

  • [2023-05-03 10:47:57]
  • 评测
  • 测评结果:100
  • 用时:117ms
  • 内存:8108kb
  • [2023-05-03 10:47:55]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=3e5+10,LIM=3e5,mod=998244353;
ll mypow(ll a,ll n){
	if(!n)return 1;ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;
	if(n&1)tmp=tmp*a%mod;return tmp;
}
ll myinv(ll a){
	return mypow(a,mod-2);
}
void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
ll addv(ll x,ll y){return (x+y)%mod;}
ll subv(ll x,ll y){return (x-y+mod)%mod;}

ll fact[MAXN],rfact[MAXN];

ll ans,n,m;

ll C(ll n,ll m){
	if(n<m || m<0)return 0;
	return fact[n]*rfact[m]%mod*rfact[n-m]%mod;
}

ll calc(ll x,ll y){
	return C(2*n-x-y,n-x);
}

int main(){

	fact[0]=1;rep(i,1,LIM)fact[i]=fact[i-1]*i%mod;
	rfact[LIM]=myinv(fact[LIM]);per(i,LIM-1,0)rfact[i]=rfact[i+1]*(i+1)%mod;

	cin>>n>>m;
	if(n<m){
		cout<<"0\n";
		exit(0);
	}

	ans=calc(0,0);

	ll x=0,y=0;
	rep(i,1,n){
		swap(x,y);
		x-=1;y+=1;
		if(x>n || y>n)break;
		sub(ans,calc(x,y));

		swap(x,y);
		x+=(m+1);y-=(m+1);
		if(x>n || y>n)break;
		add(ans,calc(x,y));
	}
	
	x=y=0;
	rep(i,1,n){
		swap(x,y);
		x+=(m+1);y-=(m+1);
		if(x>n || y>n)break;
		sub(ans,calc(x,y));

		swap(x,y);
		x-=1;y+=1;
		if(x>n || y>n)break;
		add(ans,calc(x,y));
	}

	cout<<ans<<endl;

    return 0;
}

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

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted
total time: 24ms
memory: 8076kb

Test #1:

score: 10
Accepted
time: 3ms
memory: 8076kb

input:

8 6

output:

1416

result:

ok 1 number(s): "1416"

Test #2:

score: 0
Accepted
time: 6ms
memory: 8072kb

input:

7 4

output:

365

result:

ok 1 number(s): "365"

Test #3:

score: 0
Accepted
time: 3ms
memory: 7944kb

input:

6 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

score: 0
Accepted
time: 3ms
memory: 7948kb

input:

8 3

output:

610

result:

ok 1 number(s): "610"

Test #5:

score: 0
Accepted
time: 3ms
memory: 7944kb

input:

5 8

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 6ms
memory: 7936kb

input:

6 6

output:

132

result:

ok 1 number(s): "132"

Subtask #2:

score: 10
Accepted
total time: 30ms
memory: 8088kb

Test #7:

score: 10
Accepted
time: 6ms
memory: 7940kb

input:

98765 98765

output:

726904819

result:

ok 1 number(s): "726904819"

Test #8:

score: 0
Accepted
time: 3ms
memory: 8088kb

input:

98765 98764

output:

726904818

result:

ok 1 number(s): "726904818"

Test #9:

score: 0
Accepted
time: 6ms
memory: 8008kb

input:

98765 98766

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 6ms
memory: 8004kb

input:

77777 77777

output:

891344339

result:

ok 1 number(s): "891344339"

Test #11:

score: 0
Accepted
time: 6ms
memory: 7940kb

input:

66667 66666

output:

152898151

result:

ok 1 number(s): "152898151"

Test #12:

score: 0
Accepted
time: 3ms
memory: 8076kb

input:

23333 23332

output:

918870869

result:

ok 1 number(s): "918870869"

Subtask #3:

score: 30
Accepted
total time: 21ms
memory: 8104kb

Test #13:

score: 30
Accepted
time: 3ms
memory: 8076kb

input:

296 120

output:

756072605

result:

ok 1 number(s): "756072605"

Test #14:

score: 0
Accepted
time: 6ms
memory: 8076kb

input:

273 111

output:

966439618

result:

ok 1 number(s): "966439618"

Test #15:

score: 0
Accepted
time: 3ms
memory: 8008kb

input:

189 233

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 3ms
memory: 7940kb

input:

239 78

output:

539465383

result:

ok 1 number(s): "539465383"

Test #17:

score: 0
Accepted
time: 0ms
memory: 8104kb

input:

179 134

output:

404324190

result:

ok 1 number(s): "404324190"

Test #18:

score: 0
Accepted
time: 6ms
memory: 8004kb

input:

299 290

output:

79974469

result:

ok 1 number(s): "79974469"

Subtask #4:

score: 20
Accepted
total time: 15ms
memory: 8108kb

Test #19:

score: 20
Accepted
time: 3ms
memory: 8008kb

input:

1999 1987

output:

518985910

result:

ok 1 number(s): "518985910"

Test #20:

score: 0
Accepted
time: 3ms
memory: 8108kb

input:

1920 789

output:

791389599

result:

ok 1 number(s): "791389599"

Test #21:

score: 0
Accepted
time: 0ms
memory: 8072kb

input:

1789 1890

output:

0

result:

ok 1 number(s): "0"

Test #22:

score: 0
Accepted
time: 0ms
memory: 7940kb

input:

1234 890

output:

188501739

result:

ok 1 number(s): "188501739"

Test #23:

score: 0
Accepted
time: 6ms
memory: 7940kb

input:

1789 666

output:

697918452

result:

ok 1 number(s): "697918452"

Test #24:

score: 0
Accepted
time: 3ms
memory: 7940kb

input:

1894 233

output:

109619909

result:

ok 1 number(s): "109619909"

Subtask #5:

score: 30
Accepted
total time: 27ms
memory: 8076kb

Test #25:

score: 30
Accepted
time: 6ms
memory: 8076kb

input:

99979 99891

output:

504277889

result:

ok 1 number(s): "504277889"

Test #26:

score: 0
Accepted
time: 6ms
memory: 7980kb

input:

89790 91332

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 6ms
memory: 8076kb

input:

78989 23333

output:

406026076

result:

ok 1 number(s): "406026076"

Test #28:

score: 0
Accepted
time: 0ms
memory: 8072kb

input:

98765 66666

output:

561129284

result:

ok 1 number(s): "561129284"

Test #29:

score: 0
Accepted
time: 6ms
memory: 8008kb

input:

77777 76767

output:

875062488

result:

ok 1 number(s): "875062488"

Test #30:

score: 0
Accepted
time: 3ms
memory: 8000kb

input:

92345 12345

output:

480327872

result:

ok 1 number(s): "480327872"

Extra Test:

score: 0
Extra Test Passed