Submission #1610243
Source Code Expand
#include<bits/stdc++.h> #define REP(i,m) for(int i=0;i<(m);++i) #define REPN(i,m,in) for(int i=(in);i<(m);++i) #define ALL(t) (t).begin(),(t).end() #define CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; #ifndef ONLINE_JUDGE #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl #define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} #else #define dump(x) ; #define dumpR(x) ; #define dumpY(x) ; #define dumpG(x) ; #define prl ; template<class T> void debug(T a,T b){ ;} #endif template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<int,int> pi; namespace std{ template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.fr<<','<<a.sc<<')'; return out; } } template<lint mod> struct Int_{ unsigned x; unsigned mpow(Int_ a,unsigned k){ Int_ res=1; while(k){ if(k&1) res=res*a; a=a*a; k>>=1; } return res.x; } unsigned inverse(Int_ a){ return mpow(a,mod-2); } Int_(): x(0) { } Int_(long long sig) { int sigt=sig%mod; if(sigt<0) sigt+=mod; x=sigt; } unsigned get() const { return (unsigned)x; } Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; } Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; } Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; } Int_ &operator=(Int_ that) { x=that.x; return *this;} Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;} bool operator==(Int_ that) const { return x==that.x; } bool operator!=(Int_ that) const { return x!=that.x; } Int_ operator-() const { return Int_(0)-Int_(*this);} Int_ operator+(Int_ that) const { return Int_(*this) += that; } Int_ operator-(Int_ that) const { return Int_(*this) -= that; } Int_ operator*(Int_ that) const { return Int_(*this) *= that; } Int_ operator/(Int_ that) const { return Int_(*this) /= that; } Int_ inv(){ return Int_(mpow(x,mod-2)); } }; namespace std{ template<lint mod> ostream &operator <<(ostream& out,const Int_<mod>& a){ out<<a.get(); return out; } template<lint mod> istream &operator >>(istream& in,Int_<mod>& a){ in>>a.x; return in; } }; typedef Int_<998244353> Int; Int mpow(Int a,lint k){ Int res=1; while(k){ if(k&1) res=res*a; a=a*a; k>>=1; } return res; } Int fact[1000005],invf[1000005]; Int inv[1000005]; Int C(int a,int b){ if(a<0 || b<0 || a<b) return 0; return fact[a]*invf[b]*invf[a-b]; } int main(){ #ifdef LOCAL_REDIR freopen("/home/hog/Dropbox/pg/working/in.txt","r",stdin); #endif int h,w;cin>>h>>w; if(h>w) swap(h,w); const int M=1000002; fact[0]=1; REP(i,M) fact[i+1]=fact[i]*(i+1); invf[M]=fact[M].inv(); for(int i=M-1;i>=0;--i) invf[i]=invf[i+1]*(i+1); REP(i,M) inv[i+1]=fact[i]*invf[i+1]; Int res=0; Int cur=0; for(int i=1;i<=h+w;++i){ if(i==1){ cur=C(h+w-1,w-1); }else{ if(i%2==0){ int px=i/2-1,py=i/2; cur=cur+C(px-1+py,py)*C(h+w-1-px-py,h-py); }else{ int px=i/2-1,py=i/2+1; cur=cur-C(px+py-1,px)*C(h+w-1-px-py,h-py); } // if(i-1>w){ // int px=w,py=(i-1)-w; // cur-=C(px+py-1,px); // } } res+=cur; } for(int i=1;i<h+h;++i){ if(i==1){ cur=C(h+w-1,h-1); }else{ if(i%2==0){ int px=i/2,py=i/2-1; cur=cur-C(px-1+py,py)*C(h+w-1-px-py,w-px); }else{ int px=i/2,py=i/2; cur=cur+C(px+py-1,px)*C(h+w-1-px-py,w-px); } // if(i-1>h){ // int px=(i-1)-h,py=h; // cur-=C(px+py-1,py); // } } res+=cur; } res/=C(h+w,h); cout<<res<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Yes or No |
User | hogloid |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 4381 Byte |
Status | AC |
Exec Time | 45 ms |
Memory | 11904 KB |
Judge Result
Set Name | Sample | Partial | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt |
Partial | sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 17 ms | 11904 KB |
sample_02.txt | AC | 17 ms | 11904 KB |
sample_03.txt | AC | 17 ms | 11904 KB |
sample_04.txt | AC | 16 ms | 11904 KB |
sample_05.txt | AC | 17 ms | 11904 KB |
subtask_1_01.txt | AC | 17 ms | 11904 KB |
subtask_1_02.txt | AC | 17 ms | 11904 KB |
subtask_1_03.txt | AC | 16 ms | 11904 KB |
subtask_1_04.txt | AC | 17 ms | 11904 KB |
subtask_1_05.txt | AC | 16 ms | 11904 KB |
subtask_1_06.txt | AC | 17 ms | 11904 KB |
subtask_1_07.txt | AC | 16 ms | 11904 KB |
subtask_1_08.txt | AC | 17 ms | 11904 KB |
subtask_1_09.txt | AC | 16 ms | 11904 KB |
subtask_1_10.txt | AC | 17 ms | 11904 KB |
subtask_1_11.txt | AC | 17 ms | 11904 KB |
subtask_1_12.txt | AC | 17 ms | 11904 KB |
subtask_1_13.txt | AC | 17 ms | 11904 KB |
subtask_1_14.txt | AC | 18 ms | 11904 KB |
subtask_1_15.txt | AC | 23 ms | 11904 KB |
subtask_1_16.txt | AC | 23 ms | 11904 KB |
subtask_1_17.txt | AC | 22 ms | 11904 KB |
subtask_1_18.txt | AC | 22 ms | 11904 KB |
subtask_1_19.txt | AC | 22 ms | 11904 KB |
subtask_1_20.txt | AC | 23 ms | 11904 KB |
subtask_1_21.txt | AC | 22 ms | 11904 KB |
subtask_1_22.txt | AC | 22 ms | 11904 KB |
subtask_1_23.txt | AC | 22 ms | 11904 KB |
subtask_1_24.txt | AC | 22 ms | 11904 KB |
subtask_1_25.txt | AC | 22 ms | 11904 KB |
subtask_2_01.txt | AC | 17 ms | 11904 KB |
subtask_2_02.txt | AC | 17 ms | 11904 KB |
subtask_2_03.txt | AC | 17 ms | 11904 KB |
subtask_2_04.txt | AC | 45 ms | 11904 KB |
subtask_2_05.txt | AC | 45 ms | 11904 KB |
subtask_2_06.txt | AC | 45 ms | 11904 KB |
subtask_2_07.txt | AC | 45 ms | 11904 KB |
subtask_2_08.txt | AC | 45 ms | 11904 KB |
subtask_2_09.txt | AC | 45 ms | 11904 KB |
subtask_2_10.txt | AC | 45 ms | 11904 KB |
subtask_2_11.txt | AC | 44 ms | 11904 KB |
subtask_2_12.txt | AC | 45 ms | 11904 KB |
subtask_2_13.txt | AC | 45 ms | 11904 KB |
subtask_2_14.txt | AC | 44 ms | 11904 KB |
subtask_2_15.txt | AC | 45 ms | 11904 KB |
subtask_2_16.txt | AC | 44 ms | 11904 KB |
subtask_2_17.txt | AC | 44 ms | 11904 KB |
subtask_2_18.txt | AC | 42 ms | 11904 KB |
subtask_2_19.txt | AC | 38 ms | 11904 KB |
subtask_2_20.txt | AC | 22 ms | 11904 KB |
subtask_2_21.txt | AC | 22 ms | 11904 KB |
subtask_2_22.txt | AC | 22 ms | 11904 KB |
subtask_2_23.txt | AC | 22 ms | 11904 KB |
subtask_2_24.txt | AC | 22 ms | 11904 KB |
subtask_2_25.txt | AC | 25 ms | 11904 KB |
subtask_2_26.txt | AC | 22 ms | 11904 KB |
subtask_2_27.txt | AC | 22 ms | 11904 KB |
subtask_2_28.txt | AC | 23 ms | 11904 KB |
subtask_2_29.txt | AC | 23 ms | 11904 KB |
subtask_2_30.txt | AC | 27 ms | 11904 KB |
subtask_2_31.txt | AC | 31 ms | 11904 KB |
subtask_2_32.txt | AC | 44 ms | 11904 KB |
subtask_2_33.txt | AC | 44 ms | 11904 KB |
subtask_2_34.txt | AC | 45 ms | 11904 KB |
subtask_2_35.txt | AC | 44 ms | 11904 KB |
subtask_2_36.txt | AC | 44 ms | 11904 KB |
subtask_2_37.txt | AC | 29 ms | 11904 KB |
subtask_2_38.txt | AC | 24 ms | 11904 KB |
subtask_2_39.txt | AC | 43 ms | 11904 KB |
subtask_2_40.txt | AC | 26 ms | 11904 KB |