石河子做网站,专用主机网站建设,山西建设工程协会网站,seo就是搜索引擎广告正题
评测记录#xff1a;https://www.luogu.org/recordnew/lists?uid52918pidP1879 大意
有n*m的矩阵#xff0c;有些地方可以放#xff0c;有些不可以放#xff0c;不可以相邻的放#xff0c;求放置方法总数。 解题思路
先用二进制表示每一行的是否可以放置的状…正题
评测记录https://www.luogu.org/recordnew/lists?uid52918pidP1879 大意
有n*m的矩阵有些地方可以放有些不可以放不可以相邻的放求放置方法总数。 解题思路
先用二进制表示每一行的是否可以放置的状态。 然后用state[i]state[i]state[i]来表示只计算单行第iii种状态是否合法。
然后每次将状态左移和右移一位然后用运算判断是否合法就行了。
之后我们开始dp
用f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]f[i][j]表示第i行第j种状态的方案数。然后我们枚举上一行的状态kkscript typemath/tex idMathJax-Element-2449k/script然后判断两个状态是否合法。 code
#includecstdio
#includealgorithm
#define MN 4100
using namespace std;
int n,m,c,f[MN],F[14][MN],state[MN],ans,MS;
int main()
{//freopen(cowfood.in,r,stdin);//freopen(cowfood.out,w,stdout);scanf(%d%d,n,m);for (int i1;in;i)for (int j1;jm;j){ scanf(%d,c);f[i](f[i]1)c;}MS1m;for (int i0;iMS;i)state[i]!(i(i1)||i(i1));F[0][0]1;for (int i1;in;i)for (int j0;jMS;j)if (state[j](jf[i])j)for (int k0;kMS;k)if (!(kj))F[i][j](F[i][j]F[i-1][k])%100000000;for (int i0;iMS;i)ans(ansF[n][i])%100000000;printf(%d,ans);
}
