| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #621184 | #424. 【集训队作业2018】count | Cry_For_theMoon | 100 | 117ms | 8108kb | C++ 14 | 1.6kb | 2023-05-03 10:47:55 | 2023-05-03 10:47:57 |
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

鄂公网安备 42010202000505 号