mcfx's blog - 矩阵快速幂
/category/jzk/
-
BZOJ 2432: [Noi2011]兔农
/archives/156/
2016-12-20T09:03:00+08:00
###Description
农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子?
聪明的你可能已经发现,第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数,但他也发现了规律:第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为:
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快,期待养兔子一定能赚大钱,于是栋栋在第一个月初买了一对小兔子开始饲养。
每天,栋栋都要给兔子们喂食,兔子们吃食时非常特别,总是每k对兔子围成一圈,最后剩下的不足k对的围成一圈,由于兔子特别害怕孤独,从第三个月开始,如果吃食时围成某一个圈的只有一对兔子,这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子,那么每个月的兔子数仍然是可以计算的。例如,当k=7时,前几个月的兔子数依次为:
1 1 2 3 5 7 12 19 31 49 80 …
给定n,你能帮助栋栋计算第n个月他有多少对兔子么?由于答案可能非常大,你只需要告诉栋栋第n个月的兔子对数除p的余数即可。
###Input
输入一行,包含三个正整数n, k, p。
###Output
输出一行,包含一个整数,表示栋栋第n个月的兔子对数除p的余数。
###Sample Input
6 7 100
###Sample Output
7
###Solution
按模k余数写出数列,则为
1,1,...,a,0,
a,a,...,b,0,
b,b,...,c,0,
...
这个数列最后有可能每一排首项循环,也有可能不再出现0
每次求a的逆元,则其在fib数列中首次出现位置就是a后面下一个0的位置,如果没有0特判
###Code
```c++
#include
typedef long long ll;
#define fo0(i,n) for(int i=0,i##end=n;i=s[tt].len;n-=s[tt++].len)r*=s[tt].x;
return r*pow((mat){0,1,0,1,1,0,0,0,1},n);
}
int main()
{
scanf("%lld%d%d",&n,&k,&p);
for(int i=3;;i++)
{
f[i]=f[i-1]+f[i-2];
if(f[i]>=k)f[i]-=k;
if(!pos[f[i]])pos[f[i]]=i;
if(f[i]==1&&f[i-1]==0)break;
}
int ns=1,sc=1;
for(;!p2[ns];sc++)
{
s[sc].st=ns;
p2[ns]=sc;
int t1,t2;
exgcd(k,ns,t1,t2);
if(t2
-
BZOJ 1009: [HNOI2008]GT考试
/archives/21/
2016-09-09T20:13:00+08:00
###Description
阿申准备报名参加GT考试,准考证号为N位数X1X2....Xn(0