mcfx's blog - 2017年6月

mcfx's blog - 2017年6月 /2017/06/ zh-CN 个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ Fri, 09 Jun 2017 01:01:00 +0800 Fri, 09 Jun 2017 01:01:00 +0800 BZOJ 4926: 皮皮妖的递推 /archives/238/ /archives/238/ Fri, 09 Jun 2017 01:01:00 +0800 admin

###Description
YOUSIKI学习了递推，于是他请皮皮妖给他出道题，皮皮妖说：
f(1)=1，f(i)=i-f(i-1)，求f(n)
YOUSIKI看了一眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说：
f(1)=1，f(i)=i-f(f(i-1))，求f(n)
YOUSIKI看了两眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说：
f(1)=1，f(i)=i-f(f(f(i-1)))，求f(n)
YOUSIKI看了三眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说：
...
...
...
YOUSIKI看了m眼，但是没有能秒切，于是他找到你，请你帮他解决这个问题。

###Input
一行两个正整数n,m。n<=10^18，m<=10^6

###Output
一行一个整数f(n)

###Sample Input
4 2

###Sample Output

###HINT
样例解释：f(1)=1，f(2)=2-f(f(1))=1，f(3)=3-f(f(2))=2，f(4)=4-f(f(3))=3

###Solution
为了描述简洁，把 $$f(f(..f(i)..))$$ 记为 $$f^x(i)$$。
显然，$$f(i)-f(i-1)=0\ or\ 1$$，设 $$h(i)$$ 表示最大的 $$x$$，使得对于任意 $$j\in [1,x]$$，$$f^j(i)\neq f^j(i-1)$$。
可以发现 $$f$$ 的转移可以表示为：
$$f(1)=f(2)=1$$，对于 $$i\ge 3$$，若 $$h(i-1)\ge m$$，那么 $$f(i)=f(i-1),h(i)=0$$，否则 $$f(i)=f(i-1)+1,h(i)=h(f(i))+1$$（正确性显然）。
如果有办法求出 $$h$$，那么 $$f(i)=\sum_j^i[h(j)\le m-1]-1(i\neq 1)$$。

假设 $$m=4$$，将 $$h$$ 的表列出：
```
0 0 1 2 3 4 0 5 0 1 6 0 1 2 7 0 1 2 3 8
```
换一种写法：
```
0
0
1
2
3
4 0
5 0 1
6 0 1 2
7 0 1 2 3
8 0 1 2 3 4 0
9 0 1 2 3 5 0 4 0 1
```
可以发现从第二行开始（首行记为第 $$0$$ 行），每一行是把上一行的数复制一遍，加 $$1$$，然后在每个 $$\ge m$$ 的数后面加上 $$0$$ 得到的（正确性显然）。
如果把 $$\ge m$$ 的数都写成 $$m$$，那么表会变成这样：
```
0
0
1
2
3
4 0
4 0 1
4 0 1 2
4 0 1 2 3
4 0 1 2 3 4 0
4 0 1 2 3 4 0 4 0 1
```
可以发现对于 $$i>m$$，第 $$i-1$$ 行是第 $$i$$ 行的前缀，且第 $$i$$ 行多出的部分是第 $$i-m$$ 行的内容（可使用数学归纳法证明）。

回到原问题，现在需要求 $$\sum_i^n[h(i)\le m-1]$$。
$$1$$ 到 $$n$$ 的 $$h$$ 一定包含若干整行和最后不满一行的部分。
对于每一行，可以用 $$a(i)$$ 表示这一行数的总数，$$b(i)$$ 表示这一行 $$\le m-1$$ 的数的个数。
显然，$$a(i)=b(i)=1(0\le i\le m),a(m+1)=2,b(m+1)=1$$，当 $$i\ge m+2$$ 时，$$a(i)=a(i-1)+a(i-m),b(i)=b(i-1)+b(i-m)$$。
事实上 $$b(i)$$ 并没有必要计算，因为 $$b(i)=a(i-1)$$。

这样已经可以解决前面的整行了。
对于后面不满一行的部分，可以从最后一行开始往前枚举，如果当前行的大小不超过需要的大小，那么就可以把当前行加入答案（在当前需要大小为 $$1$$ 时，需要特判只有一个 $$m$$ 的情况）。
这一部分可以由前面关于前缀的结论证明。

然后这题就完了。

<del>其他题解都直接给个莫名其妙的结论就跑，颓了几天这个题，真 $$tm$$ 爽。</del>

###Code
```c++
#include<bits/stdc++.h>

typedef long long ll;

const int N=5000007;

ll n,s,ans,a[N];
int m,i,j;

int main()
{
	scanf("%lld%d",&n,&m);
	if(n==1)return puts("1"),0;
	if(n<=m+2)return printf("%lld",n-1),0;
	for(i=0;i<=m;i++)a[i]=1;
	a[m+1]=2;
	s=m+4;
	for(i=m+2;s<=n;i++)
		s+=a[i]=a[i-1]+a[i-m];
	i--;
	for(j=0;j+1<i;j++)ans+=a[j];
	n-=s-a[i];
	for(;n>1;i--)
		if(n>=a[i])n-=a[i],ans+=a[i-1];
	printf("%lld",ans+1);
}
```

]]> 6 /archives/238/#comments /feed/archives/238/