bzoj 3823:定情信物

25199 ワード

各n次元超立方体のk次元要素を考慮した「対角線」ベクトルは、n次元からk次元を選択し、各次元は+1または−1であり、答えはC(n,k)*2^kであり、逆元を前処理した後にO(n)を得ることができる.
しかしpは
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 10000000
using namespace std;
ll rev[N];
int p;
void get_rev(int n)
{
int t=min(n,p-1);
rev[1]=1;
for (int i=2;i<=t;i++) rev[i]=rev[p%i]*(p-p/i)%p;
}
ll kpow(ll a,int b)
{
ll ans=1;
while (b)
{
if (b&1) ans=ans*a%p;
a=a*a%p; b>>=1;
}
return ans%p;
}
int main()
{
int n;
scanf("%d%d",&n,&p);
if (p==2) { printf("1
"
); return 0;}
get_rev(n);
ll ans=kpow(2,n); int sum=ans,cnt=0;
for (int i=1;i<=n;i++)
{
int tmp=n-i+1; while (tmp%p==0) cnt++,tmp/=p;
ans=ans*tmp%p;
tmp=i; while (tmp%p==0) cnt--,tmp/=p;
ans=ans*rev[tmp%p]%p;
ans=ans*rev[2]%p;
sum^=cnt?0:ans;
}
printf("%d
"
,sum);
return 0;
}

HOME Back