/category/hhh/ /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 /archives/83/ 2016-11-27T12:35:00+08:00 ###Description 给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。 操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足： 1.X和Y没有交集 2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献 相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki 操作2：修改一个区间l,r之间的数，使得所有l /archives/70/ 2016-11-09T12:55:00+08:00 ###Description XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X说，要有数列，于是便给定了一个正整数数列。 第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 ###Input 第一行一个整数n，代表数列中数的个数。 第二行n个正整数，表示初始状态下数列中的数。 第三行一个整数m，表示有m次操作。 接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。 ###Output 对于询问操作，每行输出一个回答。 ###Sample Input 10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8 ###Sample Output 19 7 6 ###Solution 显然，一个数最多开根6次就会变成1 那么直接用线段树维护区间最大值，每次暴力修改即可 ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back int n,t=1; ll s[270000],ma[270000]; inline void up(int x) { s[x]=s[x /archives/57/ 2016-10-21T00:08:00+08:00 ###Description 小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式： ![1.jpg][1] 小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出 的值，如果当N很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？ ###Input 输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行一个非负整数N。 ###Output 输出文件共包含T行。 第i行应包含一个不含多余前缀0的数，它的值应等于An(n为输入数据中第i+1行被读入的整数) ###Sample Input 3 1 3 10 ###Sample Output 1 2 3 ###HINT T=1; if(!a[len-1])len--; } inline void plus(const hjd &x) { rep(len,x.len); for(int i=0;ibas)a[i]-=bas,a[i+1]++; } if(a[len])len++; } inline void print() { printf("%d",a[len-1]); for(int i=len-2;i>=0;i--) printf("%09d",a[i]); printf("\n"); } }; struct hjd_hash { size_t operator ()(const hjd &x)const//乱搞哈希 { int ans=0; for(int i=0;i /archives/17/ 2016-09-08T22:30:00+08:00 ###Description 如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图： ![1.jpg][1] 给出n, d，编程数出深度为d的n元树数目。 ###Input 仅包含两个整数n, d(0 < n /archives/3/ 2016-09-07T23:02:00+08:00 ###Description 轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 ![bzoj1002.p1.png][1] N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示 ![bzoj1002.p2.png][2] 现给定n(Na/2)b=a-b; for(int i=0;ia-b;i--)mul(i); for(int i=2;i=0;i--) { if(is0&&k[i]) { is0=false; printf("%d",k[i]); } else if(!is0) { printf("%07d",k[i]); } } } int main() { int n; scanf("%d",&n); for(int i=1;i