Submission #3419902

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
int main()
{
	int n, m;
	cin>>n>>m;
	ll dp[16][1<<15];
	vector<int> v;
	for(int i=0; i<(1<<n); i++){
		bool ok=1;
		for(int j=0; j<n-1; j++){
			if((i&(1<<j)) && (i&(1<<(j+1)))){
				ok=0;
				break;
			}
		}
		if(ok){
			dp[0][i]=1;
			v.push_back(i);
		}else{
			dp[0][i]=0;
		}
	}
	for(int i=1; i<m; i++){
		for(auto x:v){
			dp[i][x]=0;
			for(auto y:v){
				bool ok=1;
				for(int j=0; j<n; j++){
					if((x&(1<<j)) && (y&(1<<j))){
						ok=0;
						break;
					}
				}
				if(!ok) continue;
				for(int j=0; j<n-1; j++){
					if((x&(1<<j)) && (y&(1<<(j+1)))){
						ok=0;
						break;
					}
					if((x&(1<<(j+1))) && (y&(1<<j))){
						ok=0;
						break;
					}
				}
				if(ok){
					dp[i][x]+=dp[i-1][y];
					dp[i][x]%=MOD;
				}
			}
		}
	}
	ll ans=MOD-1;
	for(auto x:v){
		ans+=dp[m-1][x];
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result