Description：

一个 $k$ 维空间，刚开始在 $(0,0,\dots,0)$ ，每次随机往一个方向走一格，问随机走了 $n$ 步之后能经过的不同位置个数的期望，乘上 $2^k$ 的值 $\%p$ 的结果。

$1\leqslant n\leqslant 2000,1\leqslant k\leqslant 10$

Solution：

神奇的 $dp$ ，设 $f[i]$ 表示走的第 $i$ 步产生了一个新位置的概率，那么答案显然等于 $\sum f[i]$ ，然后转移就是枚举第一次走到这个位置的步数然后减掉对应的概率，也就是说先与处理一个 $circ[i]$ 表示经过 $i$ 步又回到了这个点的概率，这中间可以多次经过这个点，然后转移方程为： $$ f[i]=1-\sum_{j=1}^{\lfloor\frac i 2\rfloor}f[i-j\times 2]\times circ[j\times 2] $$ 然后这题就做完了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k,mod;

#define MAXN 2010

int C[MAXN][MAXN];

#define MAXK 12

int circ[MAXN][MAXK];

int f[MAXN],pows[MAXN];

int main()

{

	scanf("%d%d%d",&n,&k,&mod);

	C[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		C[i][i] = C[i][0] = 1;

		for(int j = 1;j < i;++j)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;

	}

	for(int i = 0;i <= n;i += 2)circ[i][1] = C[i][i / 2];

	for(int i = 2;i <= k;++i)

		for(int x = 0;x <= n;x += 2)

			for(int y = 0;y <= x;y += 2)

				circ[x][i] = (circ[x][i] + 1ll * circ[x - y][i - 1] * circ[y][1] % mod * C[x][y] % mod) % mod;

	pows[0] = 1;f[0] = 1;

	for(int i = 1;i <= n;++i)

	{

		pows[i] = 1ll * pows[i - 1] * 2 * k % mod;

		f[i] = pows[i];

		for(int j = 1;j <= i / 2;++j)f[i] = (f[i] - 1ll * f[i - 2 * j] * circ[2 * j][k] % mod + mod) % mod;

	}

	int ans = 0;

	for(int i = 0;i <= n;++i)ans = (ans + 1ll * f[i] * pows[n - i] % mod) % mod;

	cout << ans << endl;

	return 0;

}