luogu P2480 [SDOI2010]古代猪文

M_sea:这道题你分析完后就是一堆板子

废话

理解完题意后,我们要求的东西是(G^s(s=sum_{d|n} inom{n}{d}))

但是这个指数(s)算出来非常大,,,

我们可以利用费马小定理 (a^{(p-1)}equiv1(mod p)(gcd(a,p)=1))

由此我们可以得到(G^s equiv G^{s mod (p-1)}(mod p))

组合数部分可以使用(Lucas)定理求解

但是,本题的(mod-1)不是一个质数,它可以质因数分解为(2*3*4679*35617)(分别记为(p_1 p_2 p_3 p_4))

所以,我们可以对这四个质因子分别算一遍(s),记第(i)个质因子算出来的(s)为(s_i)

我们可以知道$$sequiv s_1(mod p_1)$$$$sequiv s_2(mod p_2)$$$$sequiv s_3(mod p_3)$$$$sequiv s_4(mod p_4)$$

直接上(CRT)(中国剩余腚♂理)即可求出(s)

求大佬优化常数,luogu开O2跑380ms,倒数qwq

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register

using namespace std;
const LL md=999911659;
const int _=1000000+10,N=4000000+10;
il LL rd()
{
    re LL x=0,w=1;re char ch;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int n,g;
LL jc[36010][4],cj[36010][4],cc[4];
LL p[4]={2,3,4679,35617},prm[1010][2],tt;
il LL ksm(LL a,LL b,LL mod)
{
  LL an=1;
  while(b)
    {
      if(b&1) an=(an*a)%mod;
      a=(a*a)%mod;
      b>>=1;
    }
  return an;
}
il void init()
{
  for(re int j=0;j<4;j++) jc[0][j]=cj[0][j]=1;
  for(re int i=1;i<=36000;i++)
    for(re int j=0;j<4;j++)
      jc[i][j]=(jc[i-1][j]*i)%p[j],cj[i][j]=ksm(jc[i][j],p[j]-2,p[j]);
  int nn=n,sqt=sqrt(n);
  for(re int i=2;i<=sqt&&nn;i++)
    {
      if(nn%i!=0) continue;
      prm[++tt][0]=i;
      while(nn%i==0) nn/=i,++prm[tt][1];
    }
  if(nn>1) ++prm[++tt][0]=nn,prm[tt][1]=1;
}
il LL C(int nn,int mm,int q)
{
  if(nn<mm) return 0;
  if(nn<p[q]) return ((jc[nn][q]*cj[mm][q])%p[q]*cj[nn-mm][q])%p[q];
  return (C(nn/p[q],mm/p[q],q)*C(nn%p[q],mm%p[q],q))%p[q];
}
il void work(int o,int s)   //算每个质因子的贡献
{
  if(o>tt)
    {
      for(re int j=0;j<4;j++)
        cc[j]=(cc[j]+C(n,s,j))%p[j];
      return;
    }
  for(re int i=0;i<=prm[o][1];i++)
    {
      work(o+1,s);
      s*=prm[o][0];
    }
}
il void exgcd(LL a,LL b,LL &x,LL &y)
{
  if(b==0){x=1,y=0;return;}
  exgcd(b,a%b,y,x);
  y-=a/b*x;
}
il LL CRT()
{
  LL a,b,c,a1,b1,a2,b2,x,y;
  a1=p[0],b1=cc[0];
  for(re int j=1;j<4;j++)
    {
      a2=p[j],b2=cc[j];
      a=a1,b=a2,c=b2-b1;
      exgcd(a,b,x,y);
      x=((x*c)%b+b)%b;
      b1=b1+x*a1,a1=a1*a2;
    }
  return b1;
}

int main()
{
  n=rd(),g=rd();
  if(g==md) {putchar(48);return 0;}
  init();
  work(1,1);
  printf("%lld
",ksm(g,CRT(),md));
  return 0;
}