BZOJ 3823 定情信物 遞推

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 
#include 
#include 
#include 
#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<