while my guitar gently weeps(while)「建议收藏」

大家好，欢迎来到IT知识分享网。

while my guitar gently weeps(while)

题目背景

（不保证题目背景与题意无关）

吉他自那以后就被搁置在小屋里。

他静静想着，以后要去山坡的云雾缭绕，要去河边的月光似水，哪怕是巷陌街头的熙熙攘攘。最好能登上闪光灯下的舞台，让欢呼环抱在身边，让掌声萦绕在心畔。“钿头银篦击节碎，血色罗裙翻酒污”自是每个主人的梦想，自也是每把吉他轻轻许下的愿望。

渐渐地，小屋里爬满了灰尘，树荫镂过的阳光有时溜进来，隐约着翻飞的杂尘。

吉他只细细数着几次鸡鸣，又几番夕落，心也一天天老了下去。

直到某一天，第一根琴弦轻轻挣断，那是吉他的呜噎。

这根琴弦——犹记主人第一天把弄琴弦就是从这里开始的，好奇地不停弹响这第一种天籁。每每秋日午后，坐在窗台上，阳光像现在一样明亮，杨树的叶像现在一般沙响，几曲情歌，几支小调，落下的秋叶都记得这些事。又何堪回首几度春秋，多少番喜怒哀乐，多少轮阴晴圆缺，不论什么都可以在吉他里消遣。

——断了。

直到某一天，第二根琴弦轻轻挣断，那是吉他的抽泣。

这根琴弦——犹记主人第一次拨弄心弦就是从这里开始的，坐在河畔，月影静静地浮在水面上，风吹过的水面潺潺作响，仿佛流进心房，就像他和她心跳的声音一样。只记得浪漫的曲声悠扬，飘出厚厚的芦苇荡，飘进甜甜的梦乡，是夜夜呓语，是道阻且长。

——断了。

直到某一天，第三根琴弦轻轻挣断，那是吉他的哀鸣。

这根琴弦——犹记主人第一次投趣心闲就是从这里开始的，常是暮春雨后，亦或月圆时节，拨一曲舒缓小调，执笔填一首雅趣小词，挥笔描摹一幅山水画卷，或是倾心栽培一株厌阳的小花……不知什么时候眼里的柔情变淡了，就连眼泪也不似以往咸甜；不知什么时候心性变得笨拙了，连琴弦上飞翻的手指都似乎沾染了思虑与焦灼。可终究我们都在，还同以往一样亲近，一样喜欢风吹过的声响。

——断了。

不知过了多久，主人的面庞才从小屋的门缝里钻进来——那是多么疲惫的一张脸啊，可淡淡的目光里分明看得出解脱，或许还有成长里的自得，还有重逢后的欣喜。

题目描述

又是秋末冬初，主人再次拨响了吉他残存的琴弦。主人每次从一侧弹入一个音符，每次在一根琴弦处可以发生反弹，当然也可以穿过这根琴弦。当音符第一次穿过一根边界琴弦时开始弹响，最后一次穿出边界琴弦时为曲终。

定义函数 \(f(i)\) 表示音符在琴中反弹 \(i-2\) 次的方案数，并定义 \(f(1)=1\)。

定义第零天的 \(f\) 值为 \(n\)，以后每一天都反弹上一天的 \(f\) 值的次，以此类推，持续 \(k\) 天。

问第 \(k\) 天的 \(f\) 值模 \(p\) 。

输入格式

一行三个整数 \(n,k,p\)。

输出格式

一行一个整数，表示答案。

样例

样例输入 1

7 2 1000003

样例输出 1

233

样例输入 2

7 5 1000003

样例输出 2

697759

数据范围与提示

对于 \(100\%\) 的数据，满足 \(1\le n\le 10^{10^7},0\le k\le 10^{18},1\le p\le 10^6+3\)

一句话题意

设 \(f(n)\) 表示斐波那契数列的第 \(n\) 项，给定整数 \(n,m,p\)，求 \(f^{(k)}(n)\bmod p\) 的值。

其中 \(f^{(k)}(n)\) 表示函数 \(f(n)\) 的 \(k\) 次迭代，即 \(f(f(f(\cdots f(n))))\)，共有 \(k\) 层。

solution

Subtask 1

\(p=1\)，输出 \(0\) 即可。

Subtask 2

\(k=0\)，即没有嵌套，字符串输入 \(n\)，输出 \(n\bmod p\) 的值即可。

Subtask 3

\(k=1\)，即只嵌套一次，用矩阵乘法（或直接递推），直接算出 \(f(n)\bmod p\) 的值即可。

Subtask 4

出题人也不知道为什么要设这个点。

Subtask 5

为方便，设 \(t_0=p\)。

容易发现，斐波那契数列在模意义下是有周期的，并且一定存在一个整数 \(m(2\le m\le p^2)\)，使得 \(f(m)\equiv f(1)\pmod p,f(m+1)\equiv f(2)\pmod p\)，因此我们设 \(f(n)\bmod t_0\) 意义下的周期为 \(t_1\)，\(f^{(k)}(n)\bmod t_0=f(f^{(k-1)}(n)\bmod t_1)\bmod t_0\)。

同理，一直进行下去，可以得到答案为 \(f(\cdots f(n\bmod t_k)\bmod t_{k-1}\cdots)\bmod t_0\)。

用矩阵乘法单次斐波那契复杂度为 \(\log p\)，共有 \(k\) 层嵌套，每次只需改动模数即可，每次的模数可暴力预处理（此处的复杂度见下），复杂度为 \(O(k\log p)\)。

Subtask 6

\(n=1\)，嵌套几层都是 \(1\)，输出 \(1\) 即可。

Subtask 7

出题人也不知道为什么要设这个点。

Subtask 8

在上面的基础上，我们进一步可以发现若有 \(m(m<k)\) 使得 \(t_{m}=t_{m+1}\) 则 \(t_{i}=t_{m}(m\le i\le k)\)。

因此在上面暴力算 \(t\) 数组时，算到相同时便可停止，经打表，\(m<25，t_m<10^7\)。

对于 \(k\) 范围的扩大，我们会发现 \(t_i(m\le i\le k)\) 均相同。因此我们可以使用相同的方法，从内向外按上面的方法计算，当其嵌套 \(q\) 层与 \(r(q>r)\) 层相同时，便又产生了一个新的周期，这个周期的长度由抽屉原理可知，与模数（即 \(t_m\)）同阶。

所以最终复杂度为 \(O(p\log p)\)。

std

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e6+3,K=25,Len=1e7+5;
long long n,k,mod,ans;
int t[K],id,id2,len;
char s[Len];
int book[Len];
const int siz=2;
struct mat
{
    long long a[siz][siz];
    mat(){memset(a,0,sizeof(a));}
    mat operator*(mat x)
    {
        mat ans;
        long long r;
        for(int i=0;i<siz;i++)
        {
            for(int k=0;k<siz;k++)
            {
                r=a[i][k];
                for(int j=0;j<siz;j++)
                {
                    ans.a[i][j]+=x.a[k][j]*r;
                    ans.a[i][j]%=mod;
                }
            }
        }  
        return ans;
    }
    mat operator^(long long x)
    {
        mat ans,base;
        for(int i=0;i<siz;i++) ans.a[i][i]=1;
        for(int i=0;i<siz;i++)
        {
            for(int j=0;j<siz;j++) base.a[i][j]=a[i][j]%mod;
        }
        while(x)
        {
            if(x&1) ans=ans*base;
            base=base*base;
            x>>=1;
        }
        return ans;
    }
};
long long fib(long long x)
{
    if(x==0) return 0;
    if(x==1||x==2) return 1;
    mat f,g;
    f.a[0][0]=f.a[0][1]=1;
    g.a[0][0]=g.a[0][1]=g.a[1][0]=1;
    f=f*(g^(x-2));
    return f.a[0][0];
}
void calc()
{
    for(int i=0;i<=k-1;i++)
    {
        long long a=1%t[i],b=2%t[i],c;
        t[i+1]=1;
        while((a!=1%t[i])||(b!=1%t[i]))
        {
            c=(a+b)%t[i];
            a=b;
            b=c;
            t[i+1]++;
        }
        if(t[i]==t[i+1])
        {
            id=i;
            return;
        }
    }
}
inline long long read()
{
	long long x=0,f=1;
    char ch=getchar();
	while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
	while(isdigit(ch))
    {
        x=x*10+ch-48;
        ch=getchar();
    }
	return x*f;
}
signed main()
{
    scanf("%s",s+1);
    n=0;
    id=id2=k=read();
    mod=read();
    t[0]=mod;
    calc();
    len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(k>=id) n=(n*10+s[i]-48)%t[id];
        else n=(n*10+s[i]-48)%t[k];
    }
    if(k==0)
    {
        printf("%lld\n",n);
        return 0;
    }
    ans=n;
    book[ans]=1;
    mod=t[id];
    for(long long i=k-1;i>=id;i--)
    {
        ans=fib(ans);
        if(book[ans])
        {
            id2=k-i-book[ans]+1;
            break;
        }
        book[ans]=k-i+1;
    }
    k=(k-id-book[ans]+1)%id2+id+book[ans]-1;
    for(int i=k-1;i>=0;i--)
    {
        if(i>=id) mod=t[id];
        else mod=t[i];
        ans=fib(ans);
    }
    printf("%lld\n",ans);
    return 0;
}

后话

吐槽

第一次出有难度的题。（上回那个是 \(\texttt{ycx}\) 的 \(\texttt{idea}\)）

码量小、思维套路的签到题。

部分分不太好设，因此是乱设的。不过这题这么水应该用不到。

如果有人被卡常，我深表遗憾。

（这话怎么这么熟悉）

本来验题的时候 \(\texttt{ycx}\) 发现可以用 Pollard Rho 算法来优化，使得 \(p\) 的范围扩大，并且使用高精来使得 \(k\) 与 \(n\) 同阶，但在良心出题人 \(\texttt{zkx}\) 的劝阻下，弃了这个想法。（主要是没时间）

另外你们有没有发现，这题的英文名称叫做 \(while\)，其实也在暗示此题的双重循环节（bushi

顺便推一下 \(\texttt{ycx}\) 巨佬与 \(\texttt{zkx}\) 菜鸡联合出的题（

总结

\(32\times 1+17\times 1+1\times 1+0\times 3=50\)

平均得分：\(8.33\)

略低于预期，话说为什么连一分都不想拿啊。