Submission #2123882
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define YES() printf("YES\n") #define NO() printf("NO\n") #define Yes() printf("Yes\n") #define No() printf("No\n") #define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w #define int long long //typedef long long ll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> P; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } const int INF=1e+18; const double EPS=1e-9; const int MOD=1000000007; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; signed main(){ int n,m,dp[2][1 << 15][2] = {},ans = 0,now = 0,nxt = 1; cin >> m >> n; dp[now][0][0] = 1; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ for(int k = 0;k < (1 << m);k++){ dp[nxt][k][0] = 0; dp[nxt][k][1] = 0; } for(int k = 0;k < (1 << m);k++){ if(!j){ if(!((k >> j) & 1) && !((k >> (j + 1)) & 1)) (dp[nxt][k | (1 << j)][0] += dp[now][k][0] + dp[now][k][1]) %= MOD; }else{ if(!((k >> j) & 1) && !((k >> (j - 1)) & 1) && !((k >> (j + 1)) & 1)) (dp[nxt][k | (1 << j)][0] += dp[now][k][0]) %= MOD; } (dp[nxt][k & ~(1 << j)][(k >> j) & 1] += dp[now][k][0] + dp[now][k][1]) %= MOD; } swap(now,nxt); } } for(int i = 0;i < (1 << m);i++) ans = (ans + dp[now][i][0] + dp[now][i][1]) % MOD; cout << (ans + MOD - 1) % MOD << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - 天下一有無 |
User | hoget157 |
Language | C++14 (GCC 5.4.1) |
Score | 40 |
Code Size | 1671 Byte |
Status | AC |
Exec Time | 36 ms |
Memory | 1280 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 40 / 40 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | case0, case1, case10, case100, case101, case102, case103, case104, case105, case106, case107, case108, case109, case11, case110, case111, case112, case113, case114, case115, case116, case117, case118, case119, case12, case13, case14, case15, case16, case17, case18, case19, case2, case20, case21, case22, case23, case24, case25, case26, case27, case28, case29, case3, case30, case31, case32, case33, case34, case35, case36, case37, case38, case39, case4, case40, case41, case42, case43, case44, case45, case46, case47, case48, case49, case5, case50, case51, case52, case53, case54, case55, case56, case57, case58, case59, case6, case60, case61, case62, case63, case64, case65, case66, case67, case68, case69, case7, case70, case71, case72, case73, case74, case75, case76, case77, case78, case79, case8, case80, case81, case82, case83, case84, case85, case86, case87, case88, case89, case9, case90, case91, case92, case93, case94, case95, case96, case97, case98, case99 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
case0 | AC | 2 ms | 1280 KB |
case1 | AC | 2 ms | 1280 KB |
case10 | AC | 2 ms | 1280 KB |
case100 | AC | 2 ms | 1280 KB |
case101 | AC | 4 ms | 1280 KB |
case102 | AC | 2 ms | 1280 KB |
case103 | AC | 12 ms | 1280 KB |
case104 | AC | 2 ms | 1280 KB |
case105 | AC | 3 ms | 1280 KB |
case106 | AC | 3 ms | 1280 KB |
case107 | AC | 3 ms | 1280 KB |
case108 | AC | 3 ms | 1280 KB |
case109 | AC | 3 ms | 1280 KB |
case11 | AC | 2 ms | 1280 KB |
case110 | AC | 4 ms | 1280 KB |
case111 | AC | 5 ms | 1280 KB |
case112 | AC | 5 ms | 1280 KB |
case113 | AC | 29 ms | 1280 KB |
case114 | AC | 8 ms | 1280 KB |
case115 | AC | 16 ms | 1280 KB |
case116 | AC | 9 ms | 1280 KB |
case117 | AC | 17 ms | 1280 KB |
case118 | AC | 18 ms | 1280 KB |
case119 | AC | 36 ms | 1280 KB |
case12 | AC | 2 ms | 1280 KB |
case13 | AC | 3 ms | 1280 KB |
case14 | AC | 2 ms | 1280 KB |
case15 | AC | 2 ms | 1280 KB |
case16 | AC | 2 ms | 1280 KB |
case17 | AC | 2 ms | 1280 KB |
case18 | AC | 2 ms | 1280 KB |
case19 | AC | 2 ms | 1280 KB |
case2 | AC | 2 ms | 1280 KB |
case20 | AC | 2 ms | 1280 KB |
case21 | AC | 2 ms | 1280 KB |
case22 | AC | 2 ms | 1280 KB |
case23 | AC | 2 ms | 1280 KB |
case24 | AC | 2 ms | 1280 KB |
case25 | AC | 2 ms | 1280 KB |
case26 | AC | 3 ms | 1280 KB |
case27 | AC | 2 ms | 1280 KB |
case28 | AC | 2 ms | 1280 KB |
case29 | AC | 2 ms | 1280 KB |
case3 | AC | 2 ms | 1280 KB |
case30 | AC | 2 ms | 1280 KB |
case31 | AC | 2 ms | 1280 KB |
case32 | AC | 2 ms | 1280 KB |
case33 | AC | 2 ms | 1280 KB |
case34 | AC | 2 ms | 1280 KB |
case35 | AC | 2 ms | 1280 KB |
case36 | AC | 2 ms | 1280 KB |
case37 | AC | 2 ms | 1280 KB |
case38 | AC | 2 ms | 1280 KB |
case39 | AC | 3 ms | 1280 KB |
case4 | AC | 2 ms | 1280 KB |
case40 | AC | 2 ms | 1280 KB |
case41 | AC | 9 ms | 1280 KB |
case42 | AC | 2 ms | 1280 KB |
case43 | AC | 2 ms | 1280 KB |
case44 | AC | 2 ms | 1280 KB |
case45 | AC | 2 ms | 1280 KB |
case46 | AC | 2 ms | 1280 KB |
case47 | AC | 2 ms | 1280 KB |
case48 | AC | 2 ms | 1280 KB |
case49 | AC | 2 ms | 1280 KB |
case5 | AC | 2 ms | 1280 KB |
case50 | AC | 2 ms | 1280 KB |
case51 | AC | 2 ms | 1280 KB |
case52 | AC | 6 ms | 1280 KB |
case53 | AC | 2 ms | 1280 KB |
case54 | AC | 2 ms | 1280 KB |
case55 | AC | 2 ms | 1280 KB |
case56 | AC | 2 ms | 1280 KB |
case57 | AC | 2 ms | 1280 KB |
case58 | AC | 2 ms | 1280 KB |
case59 | AC | 2 ms | 1280 KB |
case6 | AC | 2 ms | 1280 KB |
case60 | AC | 2 ms | 1280 KB |
case61 | AC | 3 ms | 1280 KB |
case62 | AC | 4 ms | 1280 KB |
case63 | AC | 7 ms | 1280 KB |
case64 | AC | 13 ms | 1280 KB |
case65 | AC | 2 ms | 1280 KB |
case66 | AC | 2 ms | 1280 KB |
case67 | AC | 2 ms | 1280 KB |
case68 | AC | 2 ms | 1280 KB |
case69 | AC | 2 ms | 1280 KB |
case7 | AC | 2 ms | 1280 KB |
case70 | AC | 2 ms | 1280 KB |
case71 | AC | 3 ms | 1280 KB |
case72 | AC | 5 ms | 1280 KB |
case73 | AC | 8 ms | 1280 KB |
case74 | AC | 2 ms | 1280 KB |
case75 | AC | 2 ms | 1280 KB |
case76 | AC | 2 ms | 1280 KB |
case77 | AC | 2 ms | 1280 KB |
case78 | AC | 2 ms | 1280 KB |
case79 | AC | 2 ms | 1280 KB |
case8 | AC | 2 ms | 1280 KB |
case80 | AC | 3 ms | 1280 KB |
case81 | AC | 2 ms | 1280 KB |
case82 | AC | 2 ms | 1280 KB |
case83 | AC | 18 ms | 1280 KB |
case84 | AC | 2 ms | 1280 KB |
case85 | AC | 2 ms | 1280 KB |
case86 | AC | 2 ms | 1280 KB |
case87 | AC | 2 ms | 1280 KB |
case88 | AC | 2 ms | 1280 KB |
case89 | AC | 2 ms | 1280 KB |
case9 | AC | 2 ms | 1280 KB |
case90 | AC | 2 ms | 1280 KB |
case91 | AC | 20 ms | 1280 KB |
case92 | AC | 2 ms | 1280 KB |
case93 | AC | 2 ms | 1280 KB |
case94 | AC | 2 ms | 1280 KB |
case95 | AC | 2 ms | 1280 KB |
case96 | AC | 2 ms | 1280 KB |
case97 | AC | 2 ms | 1280 KB |
case98 | AC | 2 ms | 1280 KB |
case99 | AC | 2 ms | 1280 KB |