【loj6142】「2017 山东三轮集训 Day6」A 结论题+Lucas定理

题解：

当奇数

发现答案就是C（n,1）^2+C(n,3)^2+。。。C(n,n)^2

倒序相加，发现就是C（2n,n）所以答案就是C(2n,n)/2

当偶数

好像并不会证

打表出来可以得到

2.当n为偶数且为4的倍数时，答案为C(2n,n)+C(n,n/2)/2

3.当n为偶数且不为4的倍数时，答案为C(2n,n)-C(n,n/2)/2

另外Claris告诉我在p较小时可以数位dp来求

先用lucas定理 C(n,m)=C(n%p,m%p)*C(n/p,m/p)

然后我们就可以把n表示成p进制

答案就是m在p进制下和对应n求C的乘积

然后我们可以数位dp这个东西

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define rint register ll

#define IL inline

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

const ll p=

;

const ll mo=

;

const ll INF=1e18;

const ll N=2e6;

ll n,cnt=,a[],jc1[N],jc2[N],f[N][][];

void gcd(ll x,ll y,ll &a,ll &b)

{

  if (y==)

  {

    a=; b=; return;

  }

  gcd(y,x%y,b,a);

  b-=a*(x/y);

}

ll C(ll x,ll y)

{

  if (x<y) return();

  return jc1[x]*jc2[y]%p*jc2[x-y]%p;

}

void jf(ll &x,ll y)

{

  x+=y;

  if (x>p) x-=p;

}

int main()

{

  cin>>n;

  while (n) a[++cnt]=n%p,n/=p;

  jc1[]=jc2[]=;

  rep(i,,p)

  {

    jc1[i]=(jc1[i-]*i)%p;

    jc1[i]=(jc1[i]+p)%p;

    ll x,y;

    gcd(i,p,x,y);

    jc2[i]=(jc2[i-]*x)%p;

    jc2[i]=(jc2[i]+p)%p;

  }

  f[cnt+][][]=;

  dep(j,cnt,)

  {

    ll tmp1j=,tmp1o=;

    rep(i,,a[j]-)

    {

      ll kk=C(a[j],i);

      kk=(kk*kk)%mo;

      if (i%)

        jf(tmp1j,kk);

      else jf(tmp1o,kk);

    }

    f[j][][]=(f[j+][][]*tmp1o%mo+f[j+][][]*tmp1j%mo)%mo;

    f[j][][]=(f[j+][][]*tmp1j%mo+f[j+][][]*tmp1o%mo)%mo;

    if (a[j]%) jf(tmp1j,); else jf(tmp1o,);

    f[j][][]+=(f[j+][][]*tmp1o%mo+f[j+][][]*tmp1j%mo)%mo;

    f[j][][]+=(f[j+][][]*tmp1j%mo+f[j+][][]*tmp1o%mo)%mo;

    if (f[j+][][]) f[j][(+a[j])%][]=;

    else f[j][a[j]%][]=;

  }

  ll ans=(f[][][]+f[][][])%mo;

  cout<<ans<<endl;

}

巴特西

【loj6142】「2017 山东三轮集训 Day6」A 结论题+Lucas定理

最新文章

热门文章