题目描述
Acwing 327
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int p = 1e9;
int M , N;
int a[15][15];
int dp[15][10000];
bool sta[10000];
int sta2[10000];
int main ()
{
scanf("%d%d" , &M , &N);
for (int i = 1 ; i <= M ; i ++ )
for (int j = 1 ; j <= N ; j ++ )
{
cin >> a[i][j];
sta2[j] = (sta2[j] << 1) + a[i][j];
}
for (int i = 0 ; i <= (1 << M) ; i ++ )
sta[i] = ((i&(i << 1)) == 0) && ((i & (i >> 1)) == 0);
dp[0][0] = 1;
for (int i = 1 ; i <= N ; i ++ )
for (int j = 0 ; j < (1 << M) ; j ++ )
if (sta[j] && (sta2[i] & j) == j)
for (int k = 0 ; k < (1 << M) ; k ++ )
if ((k & j) == 0)
dp[i][j] += dp[i-1][k] % p;
// printf ("i , j , k , dp = %d %d %d %d\n" , i , j , k , dp[i][j]);
int ans = 0;
for (int i = 0 ; i < (1 << M) ; i ++ )
{
ans += dp[N][i] % p;
}
cout << ans%p << endl;
}