Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::cin;
- using std::cout;
- using std::vector;
- const long long MOD = 1e9 + 7;
- long long bit(long long mask, long long pos) {
- return (mask >> pos) & 1;
- }
- long long bits_neighbours(long long mask, long long n) {
- for (long long i = 0; i < n - 1; ++i) {
- if (bit(mask, i) == bit(mask, i + 1)) {
- return true;
- }
- }
- return false;
- }
- int main() {
- long long n, m;
- cin >> n >> m;
- vector<vector<char> > table(n, vector<char>(m));
- for (long long i = 0; i < n; ++i) {
- for (long long j = 0; j < m; ++j) {
- cin >> table[i][j];
- }
- }
- vector<long long> mask_and(m);
- vector<long long> mask_or(m);
- for (long long i = 0; i < m; ++i) {
- long long to_and = ~0;
- long long to_or = 0;
- for (long long j = 0; j < n; ++j) {
- if (table[j][i] == '+') {
- to_or = to_or | (1 << j);
- }
- if (table[j][i] == '-') {
- to_and = to_and & ~(1 << j);
- }
- }
- mask_and[i] = to_and;
- mask_or[i] = to_or;
- }
- const long long deg = 1 << n;
- const long long ones = (1 << n) - 1;
- vector<vector<long long> > dp(m, vector<long long>(deg));
- for (long long mask = 0; mask < 1 << n; ++mask) {
- long long new_mask = (mask | mask_or[0]) & mask_and[0];
- dp[0][new_mask] = 1;
- }
- for (long long i = 1; i < m; ++i) {
- for (long long msk = 0; msk < deg; ++msk) {
- long long mask = (msk | mask_or[i]) & mask_and[i];
- if (bits_neighbours(mask, n)) {
- dp[i][mask] = dp[i - 1][mask ^ ones] % MOD;
- } else {
- dp[i][mask] = (dp[i - 1][mask] + dp[i - 1][mask ^ ones]) % MOD;
- }
- }
- }
- long long sum = 0;
- vector<bool> used(deg, 0);
- for (long long i = 0; i < deg; ++i) {
- long long mask = (i | mask_or[m - 1]) & mask_and[m - 1];
- if (!used[mask]) {
- used[mask] = true;
- sum = (sum + dp[m - 1][mask]) % MOD;
- }
- }
- cout << sum << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement