Submission #122359
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS #include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <list> #include <cassert> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define EPS 1e-9 using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll; typedef vector<string> vs; typedef long double ld; template<int MOD> struct ModInt { unsigned x; ModInt(): x(0) { } ModInt(signed sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; } //inverseを使う場合これが必要!!!!!。llを使う場合は残しとけ!暗黙に変換されて壊れる!!!! ModInt(signed long long sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; } unsigned get() const { return x; } ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0; while(b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } }; template<unsigned MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) { ModInt<MOD> r = 1; while(k) { if(k & 1) r *= a; a *= a; k >>= 1; } return r; } typedef ModInt<1000000007> mint; vector<mint> fact, factinv; void nCr_computeFactinv(const int N) { fact.resize(N+1); factinv.resize(N+1); fact[0] = 1; rer(i, 1, N) fact[i] = fact[i-1] * i; factinv[N] = fact[N].inverse(); for(int i = N; i >= 1; i --) factinv[i-1] = factinv[i] * i; } mint nCr(int n, int r) { return r > n ? 0 : fact[n] * factinv[n-r] * factinv[r]; } int W, H, X, Y, D, L; int main() { cin >> W >> H >> X >> Y >> D >> L; //4辺に対してOKなものをS(i)とすると //答え = ∩ S(i) //包除原理で nCr_computeFactinv(X * Y); mint r; rep(mask, 1<<4) { int w = X, h = Y; if(mask >> 0 & 1) w --; if(mask >> 1 & 1) w --; if(mask >> 2 & 1) h --; if(mask >> 3 & 1) h --; if(w <= 0 || h <= 0) continue; bool parity = false; rep(i, 4) if(mask >> i & 1) parity ^= 1; mint x = nCr(w * h, D) * nCr(w * h - D, L); if(!parity) r += x; else r -= x; } r *= W-X+1; r *= H-Y+1; cout << r.get() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | anta |
Language | C++ (G++ 4.6.4) |
Score | 101 |
Code Size | 3670 Byte |
Status | AC |
Exec Time | 23 ms |
Memory | 936 KB |
Judge Result
Set Name | sub | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 100 / 100 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sub | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, test_03E.txt, test_04E.txt, test_07E.txt, test_08E.txt, test_11E.txt, test_12E.txt, test_15E.txt, test_16E.txt, test_19E.txt, test_20E.txt, test_23E.txt, test_24E.txt, test_27E.txt, test_28E.txt, test_31E.txt, test_32E.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_45E.txt, test_47E.txt |
All | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03E.txt, test_04E.txt, test_05.txt, test_06.txt, test_07E.txt, test_08E.txt, test_09.txt, test_10.txt, test_11E.txt, test_12E.txt, test_13.txt, test_14.txt, test_15E.txt, test_16E.txt, test_17.txt, test_18.txt, test_19E.txt, test_20E.txt, test_21.txt, test_22.txt, test_23E.txt, test_24E.txt, test_25.txt, test_26.txt, test_27E.txt, test_28E.txt, test_29.txt, test_30.txt, test_31E.txt, test_32E.txt, test_33.txt, test_34.txt, test_35.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45E.txt, test_46.txt, test_47E.txt, test_48.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01E.txt | AC | 21 ms | 804 KB |
00_sample_02E.txt | AC | 21 ms | 800 KB |
00_sample_03E.txt | AC | 22 ms | 804 KB |
00_sample_04.txt | AC | 20 ms | 800 KB |
test_01.txt | AC | 21 ms | 852 KB |
test_02.txt | AC | 21 ms | 804 KB |
test_03E.txt | AC | 22 ms | 804 KB |
test_04E.txt | AC | 20 ms | 800 KB |
test_05.txt | AC | 20 ms | 788 KB |
test_06.txt | AC | 23 ms | 808 KB |
test_07E.txt | AC | 21 ms | 800 KB |
test_08E.txt | AC | 21 ms | 680 KB |
test_09.txt | AC | 23 ms | 756 KB |
test_10.txt | AC | 21 ms | 804 KB |
test_11E.txt | AC | 20 ms | 800 KB |
test_12E.txt | AC | 21 ms | 804 KB |
test_13.txt | AC | 21 ms | 932 KB |
test_14.txt | AC | 20 ms | 800 KB |
test_15E.txt | AC | 22 ms | 800 KB |
test_16E.txt | AC | 22 ms | 800 KB |
test_17.txt | AC | 22 ms | 928 KB |
test_18.txt | AC | 21 ms | 804 KB |
test_19E.txt | AC | 22 ms | 800 KB |
test_20E.txt | AC | 22 ms | 936 KB |
test_21.txt | AC | 22 ms | 740 KB |
test_22.txt | AC | 20 ms | 800 KB |
test_23E.txt | AC | 20 ms | 800 KB |
test_24E.txt | AC | 21 ms | 932 KB |
test_25.txt | AC | 21 ms | 816 KB |
test_26.txt | AC | 23 ms | 804 KB |
test_27E.txt | AC | 21 ms | 804 KB |
test_28E.txt | AC | 21 ms | 800 KB |
test_29.txt | AC | 21 ms | 928 KB |
test_30.txt | AC | 21 ms | 804 KB |
test_31E.txt | AC | 20 ms | 804 KB |
test_32E.txt | AC | 21 ms | 928 KB |
test_33.txt | AC | 20 ms | 932 KB |
test_34.txt | AC | 20 ms | 796 KB |
test_35.txt | AC | 21 ms | 924 KB |
test_36E.txt | AC | 22 ms | 800 KB |
test_37E.txt | AC | 22 ms | 804 KB |
test_38E.txt | AC | 21 ms | 928 KB |
test_39E.txt | AC | 21 ms | 924 KB |
test_40.txt | AC | 22 ms | 800 KB |
test_41.txt | AC | 20 ms | 932 KB |
test_42.txt | AC | 20 ms | 800 KB |
test_43.txt | AC | 23 ms | 912 KB |
test_44.txt | AC | 21 ms | 800 KB |
test_45E.txt | AC | 20 ms | 748 KB |
test_46.txt | AC | 21 ms | 800 KB |
test_47E.txt | AC | 21 ms | 680 KB |
test_48.txt | AC | 21 ms | 804 KB |