bzoj 3028 食物——生成函数

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

把式子写出来，化一化，变成 x / ((1-x)^4) ，变成几个 sigma 相乘的样子，用组合意义看一下第 n 项的系数，就是 n-1 的可以不选的划分，即 C( n-1+3,3 ) 。为了高精度方便，化成 (n+2)*(n+1)*n/6 。

别忘了取模。

注意读入高精度数字的方法。错了几次之后只会一位一位地读了……

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,base=1e2,mod=;

int a[N],b[N],c[N];

void rdn()

{

  char ch=getchar();

  while(ch>''||ch<'')ch=getchar();

  while(ch>=''&&ch<='')

    b[++b[]]=ch-'',ch=getchar();

  for(int i=b[];i>;i-=)

    a[++a[]]=(b[i-]<<)+(b[i-]<<)+b[i];

  if(b[]&)a[++a[]]=b[];

  for(int i=a[]+;i<=b[];i++)b[i]=;

}

void print(int *a)

{

  printf("%d",a[a[]]);

  for(int i=a[]-;i;i--)

    printf("%02d",a[i]);

  puts("");

}

void pls(int *b,int x)

{

  b[]+=x;

  for(int i=;i<=b[];i++)

    {

      if(b[i]<base)break;

      b[i+]+=b[i]/base;b[i]%=base;

    }

  while(b[b[]+])

    {

      b[]++;

      b[b[]+]+=b[b[]]/base;b[b[]]%=base;

    }

}

void mul()

{

  c[]=a[]+b[]-;

  for(int i=;i<=a[];i++)

    for(int j=;j<=b[];j++)

      c[i+j-]+=a[i]*b[j];

  for(int i=;i<=c[];i++)

    c[i+]+=c[i]/base,c[i]%=base;

  while(c[c[]+])

    {

      c[]++;

      c[c[]+]+=c[c[]]/base;c[c[]]%=base;

    }

  for(int i=;i<=c[];i++)

    a[i]=c[i],c[i]=;

  a[]=c[]; c[]=;

}

void div(int *a,int x)

{

  for(int i=a[];i;i--)

    {

      if(i>) a[i-]+=(a[i]%x)*base;

      a[i]/=x;

    }

  while(a[]>&&!a[a[]])a[]--;

}

void upd(int *a)

{

  for(int i=a[];i>;i--)

    a[i-]+=a[i]%mod*base;

}

int main()

{

  rdn();

  for(int i=;i<=a[];i++)b[i]=a[i];

  pls(b,);mul();

  pls(b,);mul();

  div(a,);upd(a);

  printf("%d\n",a[]%mod);

  return ;

}