bzoj 4926 皮皮妖的递推

Posted on | Views:

构造.

  • 发现这个迭代过程与斐波那契数列有相似之处,构造 $g(i)=g(i-1)+g(i-m),g(0)=1$ .
  • 把 $n$ 拆成 $k$ 个 $g_i$ 的和, $n=\sum_{i=1}^k g(a_i)$ ,则 $f_n=\sum_{i=1}^k g(a_i-1)$ .
  • 证明:将 $f$ 定义式变形得到 $f(n)+f^m(n-1)=n$ .而 $n=\sum_{i=1}^k g(a_i),f_n=\sum_{i=1}^k g(a_i-1)$ .
  • $f^2(n)=\sum_{i=1}^k g(a_i-2)$ ,依次计算,可得 $f^m(n)=\sum_{i=1}^k g(a_i-m)$ .
  • 而现在需要的是 $f^m(n-1)$ ,而 $n$ 只比 $n-1$ 多了个 $1$ ,把 $g(0)$ 设为 $1$ 即可.
  • 那么就有 $\sum_{i=1}^k g(a_i-1)+\sum_{i=1}^k g(a_i-m)=\sum_{i=1}^k g(a_i)$ .于是 $g(i)=g(i-1)+g(i-m),g(0)=1$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e6+10;
ll g[MAXN];
int main()
{
	ll n=read(),m=read();
	for(int i=0;i<=m;++i)
		g[i]=1;
	int mx=m+1;
	for(;;++mx)
	{
		g[mx]=g[mx-1]+g[mx-m];
		if(g[mx]>n)
			break;
	}
	--mx;
	ll ans=0;
	for(int i=mx;i>=1 && n;--i)
		if(n>=g[i])
			n-=g[i],ans+=g[i-1];
	cout<<ans<<endl;
	return 0;
}