// Bismi ALlah
#include "bits/stdc++.h"
using namespace std;
const int mod = (int)1e9 + 7;
int check(int a, int b, int m) {
for(int i = 1; i < m; i ++) {
vector <int> cnt(2, 0);
cnt[(a & (1 << i)) > 0] ++;
cnt[(b & (1 << i)) > 0] ++;
cnt[(a & (1 << (i - 1))) > 0] ++;
cnt[(b & (1 << (i - 1))) > 0] ++;
if(cnt[0] == cnt[1]) continue;
return 0;
}
return 1;
}
signed main () {
int n, m;
cin >> n >> m;
int dp[n][(1 << m)], k;
memset(dp, 0, sizeof(dp));
cin >> k;
map <pair <int,int>,int> setle;
for(;k>=1;k--) {
char ch;
cin >> ch;
int i, j;
cin >> i >> j;
i --, j --;
if(ch == '-') setle[{i, j}] = 0;
else setle[{i, j}] = 1;
}
for(int i = 0; i < n; i ++) {
for(int mask = 0; mask < (1 << m); mask ++) {
for(auto j : setle) {
if(j.first.first == i) {
if((((mask & (1 << j.first.second)) > 0) == j.second)) continue;
goto end;
}
}
if(i == 0) dp[i][mask] = 1;
else {
for(int mask2 = 0; mask2 < (1 << m); mask2 ++) {
if(check(mask, mask2, m)) dp[i][mask] += dp[i-1][mask2], dp[i][mask] %= mod;
}
}
//cout << i << " " << mask << " " << dp[i][mask] << "\n";
end:;
}
}
// cout << check(3, 0, 2) << "<-\n";
int ans = 0;
for(int i=0; i < (1 << m); i ++) ans += dp[n-1][i], ans %= mod;
cout << ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
762 ms |
980 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
762 ms |
980 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
