蒙德里安的梦想P10975 Mondriaan’s Dream问题概述用 1×21×2 和 2×12×1 的多米诺骨牌覆盖 n×m棋盘求方案数。n,m≤11n,m≤11。状态定义f [ i ] [ j ] f[i][j]f[i][j]前 ii行已填满且第 ii行有方块伸到第 i1i1 行的列状态为 j的方案数。j是 m位二进制数第 p位为 1表示第 p列有方块从第 ii行伸到第 i1 行。状态总数 2^m转移方程f [ i ] [ j ] ∑ f [ i − 1 ] [ k ] f[i][j]∑f[i−1][k]f[i][j]∑f[i−1][k]其中 kk是第 i−1i−1 行的伸出状态需满足不冲突(j k) 0同一列不能既有伸下来的又有伸出去的剩余空位合法s t [ j ∣ k ] t r u e j ∣ k st[j∣k]truej∣kst[j∣k]truej∣k表示第 ii行被占用的列剩余连续空位必须为偶数才能竖放预处理合法性st[state]s**t[state] 表示状态 statestate是否合法所有连续 00空位的个数均为偶数。cppbool check(int state, int w) { int cnt 0; for (int i 0; i w; i) { if (state i 1) { if (cnt 1) return false; cnt 0; } else cnt; } return (cnt 1) 0; }例m4m40(0000)0(0000) 合法3(0011)3(0011) 合法5(0101)5(0101) 非法中间有1个0。完整代码#includeiostream#includecstringusingnamespacestd;constintN12,M1N;longlongf[N][M];boolst[M];intn,m;boolcheck(intstate,intw){intcnt0;for(inti0;iw;i){if(statei1){if(cnt1)returnfalse;cnt0;}elsecnt;}return(cnt1)0;}intmain(){ios::sync_with_stdio(false);cin.tie(0);while(cinnm,n||m){memset(f,0,sizeoff);for(inti0;i1m;i)st[i]check(i,m);f[0][0]1;for(inti1;in;i)for(intj0;j1m;j)for(intk0;k1m;k)if((jk)0st[j|k])f[i][j]f[i-1][k];coutf[n][0]\n;}return0;}