程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3823 定情信物 遞推

BZOJ 3823 定情信物 遞推

編輯:C++入門知識

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<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved