g[i] |= !k << j 是什么意思？

g[]数组是用来存储每一行土地状态的，你手动模拟一下，把g[]存的数值转换成2进制，就会发现，输入中是0的地方在g[]的二进制表示中变成了1，表示这块土地不能种植，输入中是1的地方在g[]的二进制表示中变成了0，表示这块土地可以种植，例如题中的输入样例，输入的时候是

1 1 1
0 1 0

那么在g[]数组里存储的就是（把g[]里的数值转换成2进制来表示哈）

0 0 0
1 0 1

对，就是对应位置的0-1互换了 但观察一下代码，y总那个j是从0~m - 1，导致最后存到g[]里的状态其实是经过左右颠倒的，如果按照常规的0-1互换想法需要j从m - 1~0。

当然了，就算左右颠倒对结果其实是无影响的，因为在状态转移时选择的状态也是对应颠倒（可以想象就是把整个图也左右翻转了一遍）的。

对对对 我正在想这个图是颠倒的 但发现并不影响

厉害了

是的，其实就是应该m-1 ~ 0这么记录g数据

###状态转移比较简单，不预处理也行

#include<bits/stdc++.h>

using namespace std;

const int N=14,M=1<<12,mod=1e8;
int n,m;
int g[N][N];
int f[N][M];
bool check(int i,int x)
{
    for(int j=m-1,k=0;j>=0;j--,k++)
       if((x>>j&1)==1&&g[i][k]==0)
           return false;
    return !(x&(x>>1));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
       for(int j=0;j<m;j++)
           cin>>g[i][j];
    f[0][0]=1;

    for(int i=1;i<=n+1;i++)
       for(int j=0;j<1<<m;j++)
          for(int k=0;k<1<<m;k++)
          {
              if(!check(i,j)||!check(i-1,k)||(j&k)!=0) continue;
              f[i][j]=(f[i][j]+f[i-1][k])%mod;
          }
    printf("%d",f[n+1][0]);
    return 0;
}

这个复杂度最坏好像高了10倍

三篇都没说滚动数组啥意思…

忘记了，不需要枚举玉米个数，答案无需要求玉米个数，只需要枚举方案和，并且对玉米个数无要求哎，写多了

无优化代码
···
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

const int N = 15, M = 1 << N,mod = 1e8;

int f[N][N * N][M];
int e[N][N],n,m,cnt[M];

vector[HTML_REMOVED] state;
vector[HTML_REMOVED] head[M];

bool check(int x)
{
for(int i = 0; i < m; i++)
if(x >> i & 1 && x >> (i + 1) & 1)
return false;
return true;
}

int find(int x)
{
int res = 0;
for(int i = 0; i < m; i)
if(x >> i & 1) res;
return res;
}

bool check2(int u,int state)
{
for(int i = 0; i < m; i++)
{
int j = state >> i & 1;
if(!e[u][i + 1] && j)
return false;
}

return true;

}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i)
for(int j = 1; j <= m; j) cin >> e[i][j];

for(int i = 0; i < 1 << m; i++)
    if(check(i))
    {
        cnt[i] = find(i);
        state.push_back(i);
        //cout << i << " " << cnt[i] << endl;
    }

for(int i = 0; i < state.size(); i++)
    for(int j = 0; j < state.size(); j++)
    {
        int a = state[i], b = state[j];
        if((a & b)== 0)
            head[a].push_back(b);
        // cout << a << "--- " <<  endl;
        // for(int k : head[a])
        //     cout << k << " " << endl;
    }

f[0][0][0] = 1;

for(int i = 1; i <= n + 1; i++)
    for(int j = 0; j <= n * m; j++)
        for(int k = 0; k < state.size(); k++)
        {
            int a = state[k];
            if(check2(i,a))
            {
                //cout << a << " " << endl;
                for(auto b : head[a])
                    if(check2(i - 1,b))
                    {
                        if(j >= cnt[a])
                        {
                            f[i][j][a] = (f[i][j][a] + f[i - 1][j - cnt[a]][b]) % mod;
                            //cout << f[i][j][a] << endl;
                        }
                    }
            }
        }

int res = 0;
for(int i = 0; i <= n * m; i++) res = (res + f[n+1][i][0]) % mod;

cout << res;

return 0;

}
···

为什么只用判断g[i] & state[a] 而不用判断b的

关于为什么只用判断g[i] & state[a] 而不用判断b的，这是因为b作为上一层的状态，已经被判断为false了，因此这个状态的方案数一直是0，因此是否判断b已经不重要了

check确实巧妙

大佬为什么只要判断第 i 行方案合法，为什么不判断第 i - 1行是否也合法

我想是不是这样呢，当枚举到第i层状态时，i-1层状态已经枚举完了，就是说i-1层的满足 1该行不相连 2与第i行不相连 3只在肥沃的土地上种植 才被赋予了值 而不满足的被赋值为0 加了也没关系，所以不用判断第 i-1 行是否合法。

大佬的确是这样的，%%%%%

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 13, M = 1<<N, MOD = 1e8;
int n, m;
int g[N];
int dp[N][M];
vector<int> state;
bool check(int x) {
    while(x) {
        if(x&1 && x>>1&1)
            return false;
        x >>= 1;
    }
    return true;
}
int main() {
    cin >> m >> n;
    for(int i = 1; i <= m; ++i) 
        for(int j = 0; j < n; ++j){
            int x;
            cin >> x;
            g[i] += (!x<<j);    
        }
    for(int i = 0; i < 1<<n; ++i) 
        if(check(i))
            state.push_back(i);

    dp[0][0] = 1;

    for(int i = 1; i <= m; ++i) {
        for(int j = 0; j < state.size(); ++j) {//i-1
            for(int k = 0; k < state.size(); ++k) {//i
                int a = state[j], b = state[k];
                if(a&b) continue;
                if(g[i]&b)  continue;
                dp[i][b] = (dp[i][b] + dp[i-1][a]) % MOD;
            }
        }
    }
    int ans = 0;
    for(int j = 0; j < state.size(); ++j) 
        ans = (ans + dp[m][state[j]]) % MOD;

    cout << ans << endl;
    return 0;
}

但是为什么我用滚动数组优化 结果就错了呢

同问

不理解，不用head进行预处理，直接暴力，感觉这样写也没问题呀，不知道哪里的细节没有考虑好

for(int i=1;i<=n+1;i)
{
for(int j=0;j<nums.size();j)
{
f[i&1][j]=0;
if(!(mp[i]&nums[j]))
for(int k=0;k<nums.size();k++)
{
int a=nums[j],b=nums[k];
if(a&b)continue;
f[i&1][j]=(f[i&1][j]+f[i-1&1][k])%p;
}
}
}
还有一个f[i&1][j]=0的初始化

bool check(int state)
{
return !(state & state << 1);
}
楼主的check 时而左移，时而右移？？

yiyang

个人喜欢固定一种写法，养成习惯

🌈✏️酱 yyds!

%%%

#include <iostream>

using namespace std;

int main()
{
    cout << “dalao %%%”;
    return 0;
}

引号错了

abababab

hh

%%% dalao tql !!

巨巨的check函数好妙啊！

🌈✏️酱 yyds!

🌈✏️酱 yyds!