bzoj 3501 PA2008 Cliquers Strike Back —— 贝尔数

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3501

用贝尔三角预处理贝尔数，拆模数并在 \( p \) 进制下使用公式，因为这样每次角标增加的是 \( p^{k} \)；

循环使用数组非常优美！0~p 的角标背后是许多 \( p \) 的整数次幂，而角标那个数字是它的 \( p^0 \) 上的数，所以最后取 \( b[d[0]] \)；

Claris 写得太好了！http://www.cnblogs.com/clrs97/p/4714467.html

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=,mod=;

int p[]={,,,},s[][xn],f[xn],b[xn],c[xn],d[];

ll n,m;

ll pw(ll a,int b,int md)

{

  ll ret=; a=a%md;

  for(;b;b>>=,a=(a*a)%md)if(b&)ret=(ret*a)%md;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void init()

{

  f[]=f[]=s[][]=; s[][]=;

  for(int i=,x=,j;i<=p[];i++,x^=)

    for(j=,f[i]=s[x][]=s[x^][i-];j<=i;j++)

      s[x][j]=upt(s[x^][j-]+s[x][j-]);

}

int cal(ll n,int p)

{

  for(int i=;i<=p;i++)b[i]=f[i]%p;//<=

  int m=;

  while(n)d[m++]=n%p,n/=p; m--;

  for(int i=;i<=m;i++)//i=1 -> d:0~m

    for(int j=;j<=d[i];j++)//d[i]*p^k

      {

    for(int k=;k<p;k++)c[k]=(i*b[k]+b[k+])%p;

    c[p]=(c[]+c[])%p;//c[p]!

    for(int k=;k<=p;k++)b[k]=c[k];//<=!!!

      }

  return b[d[]];//id -> last digit

}

int main()

{

  scanf("%lld%lld",&n,&m); init();

  if(n<=p[]){printf("%lld\n",pw(m,f[n],mod+)); return ;}//

  ll ans=;

  for(int i=;i<=;i++)

    {

      int r=cal(n,p[i]),w=mod/p[i];

      ans=(ans+(ll)w*pw(w,p[i]-,p[i])%mod*r)%mod;//w  //%p[i]

    }

  printf("%lld\n",pw(m,ans,mod+));

  return ;

}