XXXVII.[JXOI2012]奇怪的道路
神题。
（为以示区别，题面中的\(k\)我们称作\(p\)）。
思路1.
观察到\(k\)很小，考虑状压。
设\(f[i][j][k]\)表示：
前\(i\)个位置的边已经全部连完了，位置\([i-p+1,i]\)的状态压起来是\(j\)，并且连了\(k\)条边的方案数。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[50][1<<10][50],n,m,lim,p;
int ksm(int x,int y){
int z=1;
for(;y;x=(1ll*x*x)%mod,y>>=1)if(y&1)z=(1ll*z*x)%mod;
return z;
}
int main(){
scanf("%d%d%d",&n,&m,&p),lim=1<<p;
f[0][0][0]=1;
for(int i=0;i<n;i++)for(int j=0;j<min(1<<i,lim);j++)for(int k=0;k<=m;k++){
if(!f[i][j][k])continue;
for(int g=0;g<min(1<<(i+1),lim);g++){
int diff=((g>>1)^j);
if(__builtin_parity(diff)!=(g&1))continue;
int cnt=__builtin_popcount(diff);
for(int h=k+cnt;h<=m;h+=2)(f[i+1][g][h]+=1ll*f[i][j][k]*ksm(min(i,p),(h-k-cnt)>>1)%mod)%=mod;
}
}
// for(int i=1;i<=n;i++)for(int j=0;j<min(1<<i,lim);j++)for(int k=0;k<=m;k++)printf("%d,%d,%d:%d\n",i,j,k,f[i][j][k]);
printf("%d\n",f[n][0][m]);
return 0;
}
一交，WA，\(45\%\)。
咋肥事？
因为这么连，会有重复计算的部分（因为边是无序的，同一组边集只不过因为顺序不同就会加不止一次）。
思路2.
为了凸显顺序，我们不得不考虑再增加一维。
设\(f[i][j][k][l]\)表示：
前\(i\)个位置的边已经全部连完了，连了\(k\)条边，位置\([i-p+1,i+1]\)的状态压起来是\(j\)，并且位置\(i+1\)只与\([i-p+1,i-l]\)里的点连了边的方案数。
显然，初始\(f[1][0][0][0]=1\)，答案是\(f[n][m][0][0]\)。
考虑如何转移（刷表法）。
- 我们再连一条边\((i-l-1,i+1)\)。
有\(f[i][j+1][k\operatorname{xor}2^0\operatorname{xor}2^l][l]+=f[i][j][k][l]\)。
- 连接\((i-l-1,i+1)\)之间的边已经全部连完，来到下一位。
有\(f[i][j][k][l+1]+=f[i][j][k][l]\)。
- 当\(l\)枚举完成后，
如果有\(k\)的第\(p\)位为\(0\)，则可以转移到下一位，则有
\(d[i+1][j][k<<1][\min(i,p)]+=f[i][j][k][0]\)。
复杂度\(O(nmp2^p)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,p,f[40][40][1<<10][10],lim;
int main(){
scanf("%d%d%d",&n,&m,&p),lim=(1<<(p+1));
f[1][0][0][0]=1;
for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<lim;k++){
for(int l=min(i-1,p);l;l--){
if(j<m)(f[i][j+1][k^(1<<l)^1][l]+=f[i][j][k][l])%=mod;
(f[i][j][k][l-1]+=f[i][j][k][l])%=mod;
}
if(!(k&(1<<p)))(f[i+1][j][k<<1][min(i,p)]+=f[i][j][k][0])%=mod;
}
printf("%d\n",f[n][m][0][0]);
return 0;
}