3195: [Jxoi2012]奇怪的道路

链接

思路：

　　因为一个点只会和它前后k个点连边，所以，记录下每个点的前k个点和它自己（共k+1个点）的状态，1表示奇数，0表示偶数。

　　dp[i][j][s][p]表示当前考虑到第i个点，一共连了m条边，状态为s，在前k个点中，当前考虑第p个点是否与i连边。

　　那么如果p不与i连边，之间转移到p+1即可。如果连边，那么i和p的奇偶性就会改变，j->j+1，转移。

　　点与点之间的转移要求，当前状态先i-k这个位置的状态是偶数（下一个点就无法更新i-k了），即s&1=0；

　　总之，是一道好题。

代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5  
 6 using namespace std;
 7  
 8 const int mod = 1e9+7;
 9  
10 int f[32][32][(1<<9)+10][10]; //-
11  
12 int main() {
13     int n,m,k,MaxS;
14     cin >> n >> m >> k;
15     MaxS = (1<<(k+1));
16     f[1][0][0][0] = 1;
17     for (int i=1; i<n; ++i) //-
18         for (int j=0; j<=m; ++j) 
19             for (int s=0; s<MaxS; ++s) {
20                 for (int p=0; p<k; ++p) {
21                     if (!f[i][j][s][p]) continue;
22                     (f[i][j][s][p+1] += f[i][j][s][p]) %= mod;
23                     if (j<m && i-k+1+p >= 1) (f[i][j+1][s^(1<<k)^(1<<p)][p] += f[i][j][s][p]) %= mod;
24                     if ((s&1)==0) (f[i+1][j][s>>1][0] += f[i][j][s][k]) %= mod;
25                 }
26             }
27     printf("%d",f[n][m][0][0]);
28     return 0;
29 }

参考：https://blog.csdn.net/BlackJack_/article/details/78161827