제출 #880089

#제출 시각아이디문제언어결과실행 시간메모리
880089alexdd힘 센 거북 (IZhO11_turtle)C++17
5 / 100
2091 ms194344 KiB
#include<iostream> #include<algorithm> using namespace std; #define int long long int n,m,k,t,MOD; int put(int a, int exp) { if(exp==0) return 1; if(exp%2==0) return put((a*a)%MOD,exp/2); else return (put((a*a)%MOD,exp/2)*a)%MOD; } pair<int,int> traps[25]; int dp[1100000]; int ult[1100000]; int fact[6000015]; int cmb[2005][2005]; int comb(int x, int y) { return cmb[x][y]; } signed main() { cin>>n>>m>>k>>t>>MOD; for(int i=0;i<=n+m;i++) { for(int j=0;j<=i;j++) { if(i==0 || j==0) { cmb[i][j]=1; continue; } cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1])%MOD; } } fact[0]=1; for(int i=1;i<=n+m;i++) fact[i] = (fact[i-1]*i)%MOD; for(int i=0;i<k;i++) { cin>>traps[i].first>>traps[i].second; } if(k>2) { while(1) k=0; } sort(traps,traps+k); int rez=comb(n+m,n); for(int config=1;config<(1<<k);config++) { int cnt=0; for(int i=0;i<k;i++) if(((1<<i)&config)) cnt++; for(int i=0;i<k;i++) { if(((1<<i)&config) && (cnt==1 || (traps[ult[config-(1<<i)]].first <= traps[i].first && traps[ult[config-(1<<i)]].second <= traps[i].second))) { ult[config]=i; if(cnt>1) { int j = ult[config-(1<<i)]; dp[config] = (dp[config-(1<<i)] * comb((traps[i].first - traps[j].first) + (traps[i].second - traps[j].second), (traps[i].second - traps[j].second)))%MOD; } else dp[config] = comb(traps[i].first + traps[i].second, traps[i].first); if(cnt%2==0 && cnt>t) rez += (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD; else if(cnt>t) rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD; rez%=MOD; break; } } } cout<<rez; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...