Submission #19261

#TimeUsernameProblemLanguageResultExecution timeMemory
19261kaTkaHr흑백 (kriii4_G)C++14
6 / 100
2000 ms1136 KiB
#include <stdio.h> #include<vector> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int MX = 3005, MM = 1000000007; ll pw(ll A, ll B){ ll R = 1; while(B){ if( B&1 ) R = R * A % MM; A = A * A % MM; B /= 2; } return R; } ll rv(ll A){ return pw(A, MM-2); } struct frac{ ll A, B; frac(ll A):A(A), B(1){} frac(ll a, ll b){ A = (a%MM+MM) % MM; B = (b%MM+MM) % MM; } frac(){A = 0, B = 1;} frac operator+ (const frac &l)const{ return frac((A * l.B + B * l.A) % MM, B * l.B % MM); } frac operator*(const frac &l)const{ return frac(A*l.A % MM, B*l.B % MM); } frac operator/(const frac &l)const{ return frac(A*l.B % MM, B*l.A % MM); } frac operator- (const frac &l)const{ return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM); } ll v(){ return A * rv(B) % MM; } }; frac pw(frac A, ll B){ frac R = 1; while(B){ if( B&1 ) R = R * A; A = A * A; B /= 2; } return R; } frac F[MX]; int main() { F[0] = 1; for(int i = 1; i <= 1000; i++) F[i] = F[i-1] * i; int H, W; frac _5 = frac(1, 2); scanf("%d%d", &H, &W); frac A = 0, B = 0, C = 0; for(int i = 1; i <= W; i++){ for(int j = 1; j <= W-i; j++){ int k = W-i-j; A = A + F[W] / F[i] / F[j] / F[k] * ( pw(pw(_5, i) + pw(_5, j) + 1, H) - pw(pw(_5, i) + 1, H) - pw(pw(_5, j) + 1, H) + 1 ); } } for(int i = 1; i <= W; i++){ for(int j = 1; j <= W-i; j++){ int k = W-i-j; B = B + F[W] / F[i] / F[j] / F[k] * ( pw(pw(_5, i) + pw(_5, j) + pw(_5,i+j) + 1, H) - pw(pw(_5, i) + pw(_5, j) + 1, H) ); } } for(int i = 1; i <= H; i++){ for(int j = 1; j <= H-i; j++){ int k = H-i-j; C = C + F[H] / F[i] / F[j] / F[k] * ( pw(pw(_5, i) + pw(_5, j) + pw(_5,i+j) + 1, W) - pw(pw(_5, i) + pw(_5, j) + 1, W) ); } } frac ans = B + C + A; printf("%lld\n", ans.v()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...