wordpress使用七牛云,海口网站建设优化,自己能建设网站,wordpress 搭建图库正题
题目链接:https://www.ybtoj.com.cn/contest/68/problem/3 题目大意
求有多少个nnn个点mmm条边的无向图满足
有连边的点之间编号差不超过kkk所有点的度数都为偶数 解题思路
因为kkk很小#xff0c;所以我们考虑状压一个点前kkk个点的奇偶状态。设fi,j,s,0/1f_{i,j,s,…正题
题目链接:https://www.ybtoj.com.cn/contest/68/problem/3 题目大意
求有多少个nnn个点mmm条边的无向图满足
有连边的点之间编号差不超过kkk所有点的度数都为偶数 解题思路
因为kkk很小所以我们考虑状压一个点前kkk个点的奇偶状态。设fi,j,s,0/1f_{i,j,s,0/1}fi,j,s,0/1表示到第iii个点连接了jjj条边前kkk个点奇偶状态为sss然后点iii的奇偶状态。
然后转移即可每次加一个条边即可时间复杂度O(2knm)O(2^knm)O(2knm) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N32,XJQ1e97;
int n,m,k,pw[10],f[N][N][19][2];
int main()
{freopen(graph.in,r,stdin);freopen(graph.out,w,stdout);scanf(%d%d%d,n,m,k);int MS(1k);f[1][0][0][0]1;for(int i1;in;i){int limmin(MS,(1i-1));for(int x0;xmin(k,i-1);x)for(int j0;jm;j)for(int s0;slim;s){int zs^(1x);(f[i][j1][z][1]f[i][j][s][0])%XJQ;(f[i][j1][z][0]f[i][j][s][1])%XJQ;}
// if(in)break;for(int j0;jm;j)for(int s0;sMS;s){if(s(1k-1))continue;int z(s1)(MS-1);(f[i1][j][z][0]f[i][j][s][0])%XJQ;(f[i1][j][z|1][0]f[i][j][s][1])%XJQ;}}printf(%d,f[n][m][0][0]);
}
