CLYZ-2.16

同步发布于这里
有一种爆零的美感

永不逃离

[题意]

Rick 在一个无穷大的 k 维空间，他要尽量减少自己逃离次数（每到达一个未曾经过的位置即为一次逃离）。 一开始 Rick 在 (0,0,…,0) 位置，每次 Rick 会等概率随机地往 k 个方向走一步，请问走了 n 步之后，Rick 将发生的逃离次数期望，这样 Rick 就知道有多大的可能发生逃离。 比如对于路径，Rick 经过的位置是 。 输出期望乘上 (2k)^n 之后(Rick 为了避免小数)，对 mod 取模的结果。

1 \le n \le 2000，1 \le k \le 10，0

[解法]

定义浪费步数为在某一维向两侧都走过至少一步。

设 f_i 表示走了 i 步后第一次到达某个点的方案数。

在无限制的情况下，显然答案为 (2k)^i。

再定义 w(i,j) 表示 1 \to i 浪费 2j 步的方案数，w(i,j)=\sum{w(i-1,j-p)\times w(1,p) \times C^{2p}_{2j}}。

所以 f_i=(2k)^i-\sum f_j \times w(k,\frac{i-j}{2})

最后我们发现其实答案和概率根本就无关，本质上是所有不同方案经过的不同的点的个数之和，res=\sum f_i \times (2k)^{n-i}

[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
typedef long long LL;
LL n,m,mod;
LL C[N][N],power[N],f[N],w[N][N];
void init()
{
    power[0]=1LL;
    for(int i=0;i<N;i++)
    {
        if(i)power[i]=power[i-1]*(m<<1)%mod;
        for(int j=0;j<=i;j++)
        {
            if(!j)C[i][j]=1LL;
            else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }   
    }
}
int main()
{
    freopen("runaround.in","r",stdin);
    freopen("runaround.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&mod);
    init();
    for(int i=0;(i<<1)<N;i++)w[1][i]=C[i<<1][i];
    for(int i=2;i<=m;i++)
    {
        for(int j=0;(j<<1)<=n;j++)
        {
            for(int k=j;(k<<1)<=n;k++)w[i][k]=(w[i][k]+(w[i-1][j]*C[k<<1][j<<1]%mod*w[1][k-j]%mod))%mod;
        }
    }
    for(int i=0;i<=n;i++)
    {
        f[i]=power[i];
        for(int j=1;j*2<=i;j++)f[i]=((f[i]-(f[i-(j<<1)]*w[m][j]%mod))%mod+mod)%mod;
    }
    LL res=0;
    for(int i=0;i<=n;i++)res=(res+(f[i]*power[n-i]%mod))%mod;
    printf("%lld",res);
    return 0;
}