首页 > 代码库 > 【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】定情信物 推公式+线性筛逆元(推公式法比出题人简)