HNOI2009有趣的数列

阅读原文时间：2023年07月15日阅读：1

首先next_permutation打表，发现Cat规律。

其实考试的时候这么做没什么问题，而且可以节省异常多的时间，那么现在我们来想一下why。

首先我拿模型法解释一下，我们把2n个数看成2n个人，既然分成奇数和偶数两种比较方式，那么我让他们站成两排，每一排有n个人，这n个人的身高递增，且，第二排的人必须高于第一排，那么这个问题就变成了：

有2n个身高互不相同人站成两排，每排n人，要求右边的人比左边的人高，后面的人比前面的人高，问我有几种排队方案。

这是一个Cat的模型，既然先站哪一排无所谓，我就让某个位置必须先站上第一排的人再站上第二排的人，如果我将站在第一排看做是0，站在第二排看做是1，那么既然每个1前面一定有一个比他矮的人，则一定有一个0，那么就又转化成了求0，1序列，这是一个更加经典的Cat模型。（如果这里理解不了可以上网搜搜）

然后再拿折线法解释一下，我们把偶数项看做x轴上的数，因为他们是单增的，把奇数项看做y轴上的数，由于奇数项小于与之对应偶数项，也就是不能越过y=x，函数的变化就好像只能向右走和向上走。这个问题在上一篇博客中有详细的解法。

所以我们明白它是让我们求Cat，可是P不一定是质数，逆元的问题很恶心。

所以我们采用唯一分解来做。首先线性筛筛出2n以内的所有素数，然后我们枚举每个素数，对n执行以下操作：将n不断的除以这个素数，并将商加入s变量，最终s的值就是n！在算术基本定理拆分后，这个素数的指数。举个例子：

8!=27*32*5*7，8/2=4，4/2=2，2/2=1，1/2=0。4+2+1+0=7。

20!=218……，20/2=10，10/2=5，5/2=2，2/2=1，1/2=0。10+5+2+1+0=18。

大家可以自己随便试两个。

这是为什么呢？（下述i为质数）首先1~n中含有i这个因子的数有n/i个（1），含有i2这个因子的数有n/i2个（2），……含有im这个因子的数有n/im个（m）。那么我们分层计算贡献，首先（1）中有n/i个i，加上，（2）中有2*n/i2个i，但不要忘了，我们在（1）算过每个数中的一个i，那么它们的贡献只有n/i2个i，同理，向后类推，最后n！中i的个数为∑n/pi，与上述模拟过程一致。

那么我们来证明一下复杂度，首先根据小于N的质数约有N/lnN个，我们第一层枚举的代价就是O（N/lnN），然后观察上述过程，我们的问题规模不断缩小，如上述二例，都是1/2、1/2的速度在缩小，对于其他素数类似，我们取最坏O（log2N）,那么总复杂度

O（N/lnN*log2N），这玩意换换底就是O（N/ln2），1/ln2≈1.44，撇掉，大约O（N），（这是我自己证的，网上目测没有，如果有异议请指出，应该没什么问题吧……）

然后分子加分母减拆完了拿快速幂一乘就完事了。（快速幂并不影响上述复杂度，因为qpow也是O（logk）的，就当常数大了吧）。

（底下代码有表机，勾掉的调试略多，可以用来自己见证一下上面那个算法的正确性）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,P,/*a[20],*/ans=;
/*bool check(){
for(int i=1;i<=n;i++) if(a[i*2-1]>a[i*2]) return 0;
for(int i=3;i<=n*2;i++) if(a[i]>=,x=1ll*x*x%P)
if(k&) val=1ll*val*x%P;
return val%P;
}
int main(){
//打表找规律系列。。。
/* while(1){
ans=0;
scanf("%d%d",&n,&P);
for(int i=1;i<=(n<<1);i++)
a[i]=i;
do{
if(check()) {ans++;
for(int i=1;i<=2*n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}while(next_permutation(a+1,a+1+2*n));
printf("ANS=%d\n",ans);
}*/
scanf("%d%d",&n,&P);
doprime();
for(int i=;i<=prime_num;i++){
long long s=;
for(int j=*n;j/=prime[i];) s+=j;
// cout<<"s1="<<s<<endl;
for(int j=n;j/=prime[i];) s-=j;
//cout<<"s2="<<s<<endl;
for(int j=n+;j/=prime[i];) s-=j;
// cout<<"s3="<<s<<endl;
ans=1ll*ans*qpow(prime[i],s)%P;
}
// cout<<"Okprime"<<endl;
/* for(int i=1;i<=prime_num;i++)
cout<<prime[i]<<" ";cout<<endl;*/
/* for(int i=1;i<=2*n;i++)
mulfz(i);
for(int i=1;i<=n;i++)
mulfm(i);
for(int i=1;i<=n+1;i++)
mulfm(i);*/
/* cout<<"OKfenjie"<<endl;
for(int i=1;i<=prime_num;i++)
ans=1ll*ans*qpow(prime[i],fz[i]-fm[i])%P;
cout<<"Okqpow"<<endl;*/
printf("%d",ans);
return ;
}

这道题取模，下道题高精。

手机扫一扫

移动阅读更方便

你可能感兴趣的文章