UOJ #54 时空穿梭 —— 计数+莫比乌斯反演+多项式系数

题目：http://uoj.ac/problem/54

10分还要用 Lucas 定理囧...因为模数太小了不能直接算...

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int const xn=1e5+,xm=,mod=;

int n,num,m[xm],jc[xn],jcn[xn];

ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}

void init()

{

  jc[]=; int mx=mod-;

  for(int i=;i<=mx;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[mx]=pw(jc[mx],mod-);

  for(int i=mx-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

int C(int n,int m){return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}

int lucas(int n,int m)

{

  if(m==||n<m)return ;

  return (ll)lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;

}

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

int main()

{

  int T=rd(); init();

  while(T--)

    {

      n=rd(); num=rd(); bool fl=;

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

    {

      m[i]=rd();

      if(m[i]>)fl=;

    }

      if(n==)printf("%d\n",lucas(m[],num));

    }

  return ;

}

10分

参考博客：https://www.cnblogs.com/ljh2000-jump/p/6242237.html

开头结尾思路好妙，莫比乌斯反演好套路；

忘记前缀和调了半天hhh。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int Min(int x,int y){return x<y?x:y;}

int const xn=,xm=1e5+,xc=,mod=;

int n,c,m[xn],a[xn],C[xm][xc],G[xc][xm],f[xc][xm][xn],mu[xm],cnt,pri[xm],inv2;

bool vis[xm];

ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}

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

void getpri()

{

  int mx=1e5; mu[]=;

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

    {

      if(!vis[i])pri[++cnt]=i,mu[i]=-;

      for(int j=;j<=cnt&&(ll)i*pri[j]<=mx;j++)

    {

      vis[i*pri[j]]=;

      if(i%pri[j])mu[i*pri[j]]=-mu[i];

      else break;

    }

    }

}

void init()

{

  int mx=1e5;

  for(int i=;i<=mx;i++)C[i][]=;

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

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

      C[i][j]=upt(C[i-][j]+C[i-][j-]);

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

    {

      for(int g=;g<=mx;g++)

    for(int T=g;T<=mx;T+=g)

      G[c][T]=upt(G[c][T]+C[g-][c-]*mu[T/g]);

      for(int T=;T<=mx;T++)

      for(int i=,k=;i<=;i++,k=(ll)k*T%mod)

        f[c][T][i]=(f[c][T-][i]+(ll)k*G[c][T])%mod;

    }

}

void get(int t)//(px+q)

{

  int tmp,p,q;

  memset(a,,sizeof a); a[]=;//

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

    {

      tmp=m[i]/t;

      p=upt(-(ll)tmp*(tmp+)%mod*inv2%mod);

      q=(ll)tmp*m[i]%mod;

      for(int j=i;j;j--)

    a[j]=upt((ll)a[j-]*p%mod+(ll)a[j]*q%mod);

      a[]=upt((ll)a[]*q%mod);

    }

}

int main()

{

  int T=rd(); getpri(); init(); inv2=pw(,mod-);

  while(T--)

    {

      n=rd(); c=rd(); int mn=xm,ans=;

      for(int i=;i<=n;i++)m[i]=rd(),mn=Min(mn,m[i]);

      for(int i=,nxt;i<=mn;i=nxt+)

    {

      nxt=m[]/(m[]/i);

      for(int j=;j<=n;j++)nxt=Min(nxt,m[j]/(m[j]/i));

      get(i);

      for(int j=;j<=n;j++)ans=upt(ans+(ll)a[j]*(f[c][nxt][j]-f[c][i-][j])%mod);

    }

      printf("%d\n",ans);

    }

  return ;

}