首页 > 代码库 > 【BZOJ3823】【East!模拟赛_Round5T1】定情信物 推公式+线性筛逆元(推公式法比出题人简)
【BZOJ3823】【East!模拟赛_Round5T1】定情信物 推公式+线性筛逆元(推公式法比出题人简)
题解1:
我们定义点为0维元素、线为1维元素、面为2维元素……
既然一个低维超方体在对应新轴上平移得到高一维的超方体,比如二维超方体为一个面,然后沿新出现的z轴拓展,那么一个低维元素就会增加一维变成高一维的元素,比如点变成线、线变成面、面变成体……
这样就有一个推式:
高维元素会由第一维的元素衍生、同维元素复制保留,
也就是一个超方体升维之后,高维超方体第i维元素的数量将是原超方体第i维的数量*2+(i-1)维的数量。
然后经过鬼畜的推导/撞大运的找规律,可以得到一个组合数公式,
最后加个线性筛逆元,再注意注意内存就可以过了。
题解2:
从元素的度数关系着手,存在一个规律:
一个x维元素对应的x-1维元素的数量固定不变,比如一条线永远俩点,一个面永远4个点……i维元素对应2i个(i-1)维元素。而x维元素对应的x+1维元素的数量随着维度增加而单位增加,比如二维超方体(面)中一点两线,三维(立方体)中一点三线,即:
一个x维元素在y维中对应(y-x)个(x+1)维元素。
然后根据点数的倍增,我们可以得到所求超方体的0维元素(点)的个数,然后根据公式可以推导出更高维元素的个数,这样就可以O(n)出解,不过因为取模种种,还需要一个线性筛逆元~~
我的方法就是这个,可惜……快速幂long long 写成了 int!!!!!弱死了。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 10001000 using namespace std; int n,p; long long A[2]; long long inv[N]; long long power(long long x,int k) { long long ans=1; while(k) { if(k&1)ans*=x,ans%=p; x*=x,x%=p; k>>=1; } return ans; } void getinv(int x) { inv[1]=1; for(int i=2;i<=x;i++) inv[i]=(long long)(p-p/i)*inv[p%i]%p; } int now,last; int main() { int i,j,k; scanf("%d%d",&n,&p); now=0,last=1; A[0]=power(2,n); getinv(n); long long ans=A[0]; for(i=1;i<=n;i++) { now^=1,last^=1; A[now]=A[last]*(n-i+1)%p*inv[i]%p*inv[2]%p; ans^=A[now]; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
【BZOJ3823】【East!模拟赛_Round5T1】定情信物 推公式+线性筛逆元(推公式法比出题人简)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。