BZOJ 3823 定情信物 递推

题目大意：定义点为零维元素，线为一维元素，面为二维元素，空间为三维元素，以此类推，求n维立方体中各维元素都有多少

令f[i][j]为i维立方体内j维元素的个数

考虑n维立方体中的i维元素，将n维立方体拓展至n+1维空间时(觉得抽象的可以想象平面扩展成立方体)

原先的i维元素增加了一倍，同时原先的i-1维元素变为了i维元素

故有f[i][j]=f[i-1][j]*2+f[i-1][j-1]

经过一系列的推导(我不会怎么推，我是打表之后斜着找规律的)，可以得到f[i][j]=2^(i-j)*C(i,j)

然后就有f[n][i]=f[n][i+1]*2*(i+1)/(n-i) 线性求出逆元 从后往前推即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 10001000
using namespace std;
long long inv[M],ans=1;
int n,p;
void Linear_Shaker()
{
    int i;
    inv[1]=1;
    for(i=2;i<=n;i++)
        inv[i]=(p-p/i)*inv[p%i]%p;
}
int main()
{
    int i;
    long long temp;
    cin>>n>>p;
    Linear_Shaker();
    temp=1;
    for(i=n-1;~i;i--)
    {
        temp=temp*(i+1<<1)%p*inv[n-i]%p;
        ans^=temp;
    }
    cout<<ans<<endl;
}

BZOJ 3823 定情信物 递推

原文：http://blog.csdn.net/popoqqq/article/details/42216177