QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643258#8792. CandiesKFCAC ✓2022ms4144kbC++232.4kb2024-10-15 20:10:472024-10-15 20:10:47

Judging History

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

  • [2024-10-15 20:10:47]
  • 评测
  • 测评结果:AC
  • 用时:2022ms
  • 内存:4144kb
  • [2024-10-15 20:10:47]
  • 提交

answer

// Hydro submission #670e5bc4f512b2475e9f0f31@1728994245173
/*
Reference: 
- https://qoj.ac/submission/438295
- https://oeis.org/A098273
*/
#include<bits/stdc++.h>
using namespace std;
#define ve vector
#define x first
#define y second
#define ep emplace
#define pb emplace_back
#define de(b) #b,'=',b
#define Sz(k) int((k).size())
#define all(b) begin(b),end(b)
#define rll(k) rbegin(k),rend(k)
namespace BK0717 {
#ifdef Bella
ifstream cin("BK.in"); ofstream cout("BK.out");
void clg(auto x){cerr<<x;} void clg(auto x,auto...y){clg(x),clg(y...);}
#endif
int cn(auto&x,auto y){return x>y?x=y,1:0;}
int cx(auto&x,auto y){return x<y?x=y,1:0;}
template<class T> constexpr T inf=numeric_limits<T>::max()/2;
using LL=long long; using db=double; using pii=pair<int,int>;
constexpr int N=3e4+7,P=998244353;
int inv[N];
struct Mi {
  int n; Mi(){n=0;}
  template<class T>Mi(T m){m>=P&&(m%=P),m<0&&(m+=P),n=m;}
  constexpr int&operator()(){return n;}
  Mi operator+=(Mi m){return (n+=m())<P||(n-=P),*this;}
  Mi operator-=(Mi m){return (n-=m())<0&&(n+=P),*this;}
  Mi operator*=(Mi m){return n=1LL*n*m()%P,*this;}
  Mi operator/=(Mi m){return n=1LL*n*inv[m()]%P,*this;}
  friend Mi operator+(Mi n,Mi m){return n+=m;}
  friend Mi operator-(Mi n,Mi m){return n-=m;}
  friend Mi operator*(Mi n,Mi m){return n*=m;}
  friend Mi operator/(Mi n,Mi m){return n/=m;}
  friend ostream&operator<<(ostream&os,Mi x){return os<<x();}
}fac[N],ifa[N],pw4[N];
int init_com=[] {
  pw4[0]=1;
  for(int i=1;i<N;++i) pw4[i]=pw4[i-1]*4;
  inv[1]=1;
  for(int i=2;i<N;++i) inv[i]=1LL*(P-P/i)*inv[P%i]%P;
  fac[0]=1;
  for(int i=1;i<N;++i) fac[i]=fac[i-1]*i;
  ifa[0]=1;
  for(int i=1;i<N;++i) ifa[i]=ifa[i-1]*inv[i];
  return (fac[N-1]*ifa[N-1])()==1;
} ();
Mi C(int n,int k){return n<k||k<0?0:fac[n]*ifa[n-k]*ifa[k];}
Mi C(int a,int b,int c){return fac[a+b+c]*ifa[a]*ifa[b]*ifa[c];}
Mi f(int a,int b) {
  tie(a,b)=make_pair(b,a-b);
  return pw4[a]*(2*b+1)/(a+b+1)/(2*(a+b)+1)*C(2*b,b)*C(3*a+2*b,a);
}
void Solve() {
  int a,b,c; cin>>a>>b>>c;
  Mi ans=C(a,b,c);
  for(int i=0;i<=min(a,b-1);++i) for(int j=0;j<=min(i,c);++j) ans-=f(i,j)*C(a-i,b-i-1,c-j);
  for(int i=0;i<=min(a,c-1);++i) for(int j=0;j<=min(i,b);++j) ans-=f(i,j)*C(a-i,b-j,c-i-1);
  cout<<ans;
  return;
}
void Main() {
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int T=1;
  // cin>>T;
  for(;T--;) Solve();
} } main(){BK0717::Main();}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4048kb

input:

4 3 2

output:

368

result:

ok answer is '368'

Test #2:

score: 0
Accepted
time: 2022ms
memory: 4136kb

input:

10000 10000 10000

output:

905642282

result:

ok answer is '905642282'

Test #3:

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

input:

99 99 99

output:

604759627

result:

ok answer is '604759627'

Test #4:

score: 0
Accepted
time: 1312ms
memory: 4132kb

input:

10000 9876 6543

output:

172894229

result:

ok answer is '172894229'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4112kb

input:

7 1 6

output:

5577

result:

ok answer is '5577'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4020kb

input:

28 23 17

output:

816429586

result:

ok answer is '816429586'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4076kb

input:

87 54 22

output:

401507657

result:

ok answer is '401507657'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4104kb

input:

50 40 16

output:

770938562

result:

ok answer is '770938562'

Test #9:

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

input:

72 19 53

output:

607733148

result:

ok answer is '607733148'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4048kb

input:

8 4 4

output:

325590

result:

ok answer is '325590'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4080kb

input:

65 45 14

output:

452076388

result:

ok answer is '452076388'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4080kb

input:

82 8 67

output:

708832480

result:

ok answer is '708832480'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4076kb

input:

65 10 35

output:

769016918

result:

ok answer is '769016918'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

4 3 4

output:

1408

result:

ok answer is '1408'

Test #15:

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

input:

9139 6356 279

output:

833879698

result:

ok answer is '833879698'

Test #16:

score: 0
Accepted
time: 96ms
memory: 4144kb

input:

3888 2407 1937

output:

380556889

result:

ok answer is '380556889'

Test #17:

score: 0
Accepted
time: 508ms
memory: 4104kb

input:

9161 3171 7913

output:

643956900

result:

ok answer is '643956900'

Test #18:

score: 0
Accepted
time: 27ms
memory: 4144kb

input:

1392 1354 938

output:

491399135

result:

ok answer is '491399135'

Test #19:

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

input:

5930 427 1403

output:

786969030

result:

ok answer is '786969030'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4004kb

input:

507 99 150

output:

960656496

result:

ok answer is '960656496'

Test #21:

score: 0
Accepted
time: 130ms
memory: 4084kb

input:

3119 2372 2681

output:

751161512

result:

ok answer is '751161512'

Test #22:

score: 0
Accepted
time: 206ms
memory: 4088kb

input:

6636 3688 2743

output:

839083240

result:

ok answer is '839083240'

Test #23:

score: 0
Accepted
time: 25ms
memory: 4052kb

input:

4890 475 2865

output:

788640273

result:

ok answer is '788640273'

Test #24:

score: 0
Accepted
time: 88ms
memory: 4020kb

input:

6708 663 6384

output:

426276232

result:

ok answer is '426276232'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

1 1 1

output:

2

result:

ok answer is '2'

Extra Test:

score: 0
Extra Test Passed