Submission #6440964

---

Source Code Expand

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
const int MOD = 1000000007;

int dp[101][1 << 7][1 << 8];
int main() {
    int N, L; cin >> N >> L;
    vector< vector<int> > w(10, vector<int>(1 << 8));
    for(int i=0; i<N; i++) {
        string s; cin >> s;
        reverse(s.begin(), s.end());

        int bit = 0;
        for(size_t j=0; j<s.length(); j++) {
            bit |= (s[j] - '0') << j;
        }
        w[s.length()][bit] = 1;
    }

    dp[0][0][1] = 1;
    int mask7 = (1 << 7) - 1;
    int mask8 = (1 << 8) - 1;
    for(int i=0; i<L; i++) {
        for(int j=0; j<(1<<7); j++) {
            for(int k=0; k<(1<<8); k++) {
                if(dp[i][j][k] == 0) continue;
                // fprintf(stderr, "dp[%d][%s][%s] = %d\n", i, bitset<7>(j).to_string().c_str(), bitset<8>(k).to_string().c_str(), dp[i][j][k]);
                for(int l=0; l<2; l++) {
                    int nj = (j << 1) | l;
                    int nk = (k << 1);
                    if(nk == 0) continue;
                    
                    for(int x=1; x<9; x++) {
                        if(nk >> x & 1) {
                            int mask = (1 << x) - 1;
                            int val = nj & mask;
                            if(w[x][val]) nk |= 1;
                        }
                    }

                    (dp[i+1][nj & mask7][nk & mask8] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }

    int ans = 0;
    for(int j=0; j<(1<<7); j++) {
        for(int k=0; k<(1<<8); k++) {
            if(k & 1) (ans += dp[L][j][k]) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result