首页 > 代码库 > 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 <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 定情信物 递推
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。