或者说...

是这题:http://codeforces.com/gym/100959/attachments/download/4248/20152016-petrozavodsk-winter-training-camp-makoto-rng58-soejima-sontest-4-en.pdf

没错还是这道题

感谢杨主力@FizzyDavid 翻译!(等下这题是谁翻译来着的好像是陈主力@OhWeOnFire ?)

题意:

你被丢在一个茫茫的平面上,你不知所措,为了探清楚周边的地形,以及到底发生了什么哪里有吃的哪里有水而随机走了n步,每一步都是上下左右在走

问你期望走到了多少个格子,出题人要你输出期望值*4^n mod M

Tip:原点也是个格子而且一定是走到的格子,换而言之,如果N=0也要输出一个1(虽然1<=N<=5000)

1e9 <= M <= 2e9

这题似乎需要一个long long或者unsigned int...

我这int写的是要把自己炸了一样

感谢@FizzyDavid 提供解法!

我们考虑每一步的贡献

如果第i步的贡献是x_i,那么它的总贡献就是sigma 4^(n-i) * x_i

所以..我们只要计算xi即可

x_i = 4^i - sigma(x_j * f_j)

其中f_j是任意走j步相抵消了以后的步数,当然如果j是奇数的时候答案取0

yjz神犇告诉我们,j是偶数的时候,这个值等于C(j,j/2)的平方,理由如下:

我们设定:

向上走为0,向下为3;向左是1,向右是2

那么我们取一半的+2 取一半的+1 可以恰好构造综合起来等于没走的方式

所以代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int c[5005][5005];
int modo;
int f[5005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d%d",&n,&modo);
    int i;
    int p=1;
    int ans=0;
    for (i=0;i<=n;i++)
    {
        int j;
        c[i][0]=1;
        for (j=1;j<=i;j++)
        {
            c[i][j]=((long long)c[i-1][j]+c[i-1][j-1])%modo;
        }
    }
    f[0]=1;
    ans=1;
    for (i=1;i<=n;i++)
    {
        p=(long long)p*4%modo;
        int j;
        f[i]=p;
        for (j=0;j<i;j++)
        {
            if ((i-j)&1) continue;
            int t=(long long)c[i-j][(i-j)/2]*c[i-j][(i-j)/2]%modo;
            f[i]=(f[i]-(long long)f[j]*t)%modo;
        }
        f[i]=((long long)f[i]+modo)%modo;
        ans=ans*4ll%modo;
        ans=((long long)ans+f[i])%modo;
    }
    printf("%d\n",ans);
    return 0;
}