Description：

$F(n)=1(1\le n \le k-1 ) \\ F(n)=F(n-k)+F(n/k)(n\% k =0) \\ F(n)=F(n-1)(n\%k \ne 0)$

给出 $k$ 和 $n$ ，计算 $F(n)$ 。

$2\le k \le 10,1\le n \le k^{50}$

Solution：

第一个转移如果改成 $f(0)=1$ ，意义相同。

考虑从零到 $n$ 的一条路径，由题意得包括若干次加一和若干次乘 $k$ ，不妨换一种眼光，每次加一想象成对集合添加一个一，乘 $k$ 则是对集合中所有元素乘 $k$ ，那么如果最后集合中的元素和为 $n$ ，就对答案产生一的贡献。这样每一个最终的集合对应从 $0$ 到 $n$ 的一条路径在最终的答案中有 $1$ 的贡献。

可以发现这个集合中所有元素都是 $k$ 的幂，于是问题就变成了：把 $n$ 划分为 $k$ 的幂，有多少种方案。

与整数分解成二的幂相同的是，可以设 $f[i][j]$ 表示把 $K^i$ 分解为最大是 $K^j$ 的方案数，以前每次只用合并两个，但这次一次需要合并 $k$ 个，于是再加一个 $DP$ ，设 $g[a][b]$ 表示把 $a\times K^{i-1}$ 分解为最大 $K^b$ 的方案数，转移为 $\begin{align}g[a][b]=\sum_{k=0}^bg[a-1][k]\times f[i-1][b][k]\end{align}$ ，还是像上一题一样压掉一维，于是 $\begin{align}g[a][b]=\sum_{k=0}^bg[a-1][k]\times f[i-k-1][b-k]\end{align}$ ，初值有 $g[1][j]=f[i-1][j]$ ，最后把 $f[i][j]=g[K][j]$ 。

最后统计答案也是一样，先把 $n$ 分解为 $k$ 进制，然后 $k$ 个合并。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int m;

#define MAXN 50

#define MAXM 400

#define BASE 100000000

char c[MAXN];

typedef long long ll;

ll tt[MAXM];

struct bigint

{

  int w,a[MAXM];

  bigint(){w = 0;memset(a,0,sizeof(a));}

  friend bigint operator + (bigint a,bigint b) {

    bigint t;

    t.w = max(a.w,b.w);

    for(int i = 1;i <= t.w;++i){

      t.a[i] += a.a[i] + b.a[i];

      if(t.a[i] >= BASE){

	t.a[i + 1] = 1;

	t.a[i] -= BASE;

      }

    }

    if(t.a[t.w + 1] > 0)++t.w;

    return t;

  }

  friend bigint operator * (bigint a,bigint b){

    bigint t;

    memset(tt,0,sizeof(tt));

    for(int i = 1;i <= a.w;++i){

      for(int j = 1;j <= b.w;++j){

	tt[i + j - 1] += (ll)a.a[i] * b.a[j];

      }

    }

    t.w = a.w + b.w;

    for(int i = 1;i <= t.w;++i){

      tt[i + 1] += tt[i] / BASE;

      t.a[i] = tt[i] % BASE;

    }

    for(;t.w > 1 && t.a[t.w] == 0;--t.w);

    return t;

  }

}f[MAXN + 5][MAXN + 5],ans,n,s[MAXN + 5],g[MAXN + 5][MAXN + 5],h[11][MAXN + 5];

int main(){

  scanf("%d%s",&m,c + 1);

  int l = strlen(c + 1);

  n.w = l / 8 + 1;

  for(int i = 1;i <= l;++i){

    int j = (l - i) / 8;

    n.a[j + 1] = n.a[j + 1] * 10 + c[i] - '0';

  }

  f[0][0].w = f[0][0].a[1] = 1;

  for(int i = 1;i <= MAXN;++i){

    for(int j = 0;j < i;++j)g[1][j] = f[i - 1][j];

    for(int x = 2;x <= m;++x){

      for(int j = 0;j < i;++j){

	g[x][j].w = 0;

	memset(g[x][j].a,0,sizeof(g[x][j]));

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

	  g[x][j] = g[x][j] + g[x - 1][k] * f[i - 1 - k][j - k];

      }

    }

    for(int j = 0;j < i;++j)f[i][j] = g[m][j];

    f[i][i].w = f[i][i].a[1] = 1;

  }

  memset(g,0,sizeof(g));

  g[0][0].w = g[0][0].a[1] = 1;

  for(int i = 0;i <= MAXN;++i){

    int r = 0;

    for(int j = n.w;j >= 1;--j){

      int t = n.a[j];

      n.a[j] = ((ll)r * BASE + t) / m;

      r = ((ll)r * BASE + t) % m;

    }

    for(int j = 0;j <= i;++j)h[0][j] = g[i][j];

    for(int x = 1;x <= r;++x){

      for(int j = 0;j <= i;++j){

		h[x][j].w = 0;

		memset(h[x][j].a,0,sizeof(h[x][j].a));

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

		  h[x][j] = h[x][j] + h[x - 1][k] * f[i - k][j - k];

      }

    }

    for(int j = 0;j <= i;++j)g[i + 1][j] = h[r][j];

  }

  for(int i = 0;i <= MAXN;++i)ans = ans + g[MAXN + 1][i];

  printf("%d",ans.a[ans.w]);

  for(int i = ans.w - 1;i >= 1;--i){

    for(int j = 1e7;j >= 1;j /= 10){

      printf("%d",ans.a[i] / j);

      ans.a[i] %= j;

    }

  }

  puts("");

  return 0;

}