P4295 [SCOI2003]严格N元树 DP

思路：DP

提交：\(5\)次

错因：2次高精写错（我太菜了），2次写错特判

题解：

设\(f[i]\)表示深度\(\leq i\)的严格\(n\)元树的数目，有

\[f[i]=pow(f[i-1],n)+1
\]

即一个点，对于每一个孩子深度都可以是\(1\)到\(i-1\)的严格\(n\)元树，或是仅仅一个点（作为根）。

所以最后的答案是\(f[i]-f[i-1]\)

需要高精。

#include<cstdio>

#include<iostream>

#include<cstring>

#define R register int

using namespace std;

namespace Luitaryi {

template<class I> inline I g(I& x) { x=0;

  register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;

} const int N=10010;

int n,d,a[N],b[N],f[N],mem[N],sza,szb;

inline void print(int* f,int len) {

  for(R i=len;i;--i) cout<<f[i]; cout<<endl;

}

inline void mul(int a[N],int b[N],int& sza,int szb) {

  R tmp[N]; memset(tmp,0,sizeof(tmp));

  for(R i=1;i<=sza;++i) for(R j=1;j<=szb;++j)

    tmp[i+j-1]+=a[i]*b[j];

  sza+=szb-1; for(R i=1;i<=sza;++i) tmp[i+1]+=tmp[i]/10,tmp[i]%=10;

  while(tmp[sza+1]) ++sza,tmp[sza+1]+=tmp[sza]/10,tmp[sza]%=10;

  memcpy(a,tmp,sizeof(int)*(sza+3));

}

inline void main() {

  g(n),g(d); if(d==0) return (void) puts("1"); f[1]=1,sza=1;

  for(R i=1;i<=d;++i) { memcpy(mem,f,sizeof(int)*(sza+3)),szb=sza;

    for(R j=2;j<=n;++j) mul(f,mem,sza,szb); ++f[1];

    for(R j=1;j<=sza;++j) f[j+1]+=f[j]/10,f[j]%=10;

    while(f[sza+1]) ++sza,f[sza+1]+=f[sza]/10,f[sza]%=10;

  } for(R i=1;i<=sza;++i) f[i]-=mem[i];

  for(R i=1;i<=sza;++i) if(f[i]<0) f[i]+=10,--f[i+1];

  while(!f[sza]) --sza; while(sza) printf("%d",f[sza]),--sza;

}

} signed main() {Luitaryi::main(); return 0;}

2019.08.16

84