Submission #880105

#TimeUsernameProblemLanguageResultExecution timeMemory
880105alexddEnergetic turtle (IZhO11_turtle)C++17
5 / 100
2088 ms25204 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 inde; int comb(int x, int y) { return (((((fact[x]*put(fact[y],inde-1)%MOD)*put(fact[x-y],inde-1))%MOD))); } int calc_inde(int x) { int d=2; int prod = n, imp = 1; while(d*d<=x) { if(x%d==0) { while(x%d==0) x/=d; prod *= d-1; imp *= d; } if(d==2) d--; d+=2; } if(x>1) { prod *= x-1; imp *= x; } return prod/imp; } signed main() { cin>>n>>m>>k>>t>>MOD; inde = calc_inde(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; } 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); //cout<<config<<" "<<dp[config]<<" "<<comb(n - traps[i].first + m - traps[i].second, n - traps[i].first)<<" zzz\n"; if(cnt>t) { rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD; rez%=MOD; for(int config2=0;config2<(1<<cnt)-1;config2++) { int cnt2=0; for(int u=0;u<cnt;u++) if((((1<<u)&config2))) cnt2++; if(cnt2>t) rez = (rez + (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD)%MOD; } rez%=MOD; } break; } } } cout<<rez; return 0; } /** 1 4 2 1 100000 0 3 1 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...