BZOJ 4926: 皮皮妖的递推

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

3

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$ 的情况）。
这一部分可以由前面关于前缀的结论证明。

然后这题就完了。

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

Code

#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);
}

日期： 2017-06-09

标签： BZOJ

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/238/ 查看。