mcfx's blog

题解、Writeup、游记和碎碎念

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(f(..f(i)..)) 记为 fx(i)f^x(i)
显然,f(i)f(i1)=0 or 1f(i)-f(i-1)=0\ or\ 1,设 h(i)h(i) 表示最大的 xx,使得对于任意 j[1,x]j\in [1,x]fj(i)fj(i1)f^j(i)\neq f^j(i-1)
可以发现 ff 的转移可以表示为:
f(1)=f(2)=1f(1)=f(2)=1,对于 i3i\ge 3,若 h(i1)mh(i-1)\ge m,那么 f(i)=f(i1),h(i)=0f(i)=f(i-1),h(i)=0,否则 f(i)=f(i1)+1,h(i)=h(f(i))+1f(i)=f(i-1)+1,h(i)=h(f(i))+1(正确性显然)。
如果有办法求出 hh,那么 f(i)=ji[h(j)m1]1(i1)f(i)=\sum_j^i[h(j)\le m-1]-1(i\neq 1)

假设 m=4m=4,将 hh 的表列出:

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

可以发现从第二行开始(首行记为第 00 行),每一行是把上一行的数复制一遍,加 11,然后在每个 m\ge m 的数后面加上 00 得到的(正确性显然)。
如果把 m\ge m 的数都写成 mm,那么表会变成这样:

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>mi>m,第 i1i-1 行是第 ii 行的前缀,且第 ii 行多出的部分是第 imi-m 行的内容(可使用数学归纳法证明)。

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

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

然后这题就完了。

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

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/ 查看。