BZOJ 2432: [Noi2011]兔农 December 20, 2016 ###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<bits/stdc++.h> typedef long long ll; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) void exgcd(int a,int b,int &x,int &y){if(b)exgcd(b,a%b,y,x),y-=(a/b)*x;else x=1,y=0;} ll n; int k,p,pos[1000000],f[6000010]={0,1,1},p2[1000000]; struct mat { int a[3][3]; inline void operator *=(mat x) { ll t[3][3];memset(t,0,sizeof(t)); fo0(i,3)fo0(j,3)fo0(k,3)t[i][k]+=(ll)a[i][j]*x.a[j][k]; fo0(i,3)fo0(j,3)a[i][j]=t[i][j]%p; } inline mat operator *(mat x) { mat r=*this;r*=x;return r; } }; mat pow(mat a,ll p) { mat r=(mat){1,0,0,0,1,0,0,0,1}; for(;p;p>>=1,a*=a)if(p&1)r*=a; return r; } struct data { int st,len;mat x; }s[1000001]; inline mat get(ll n,int tt) { mat r=(mat){1,0,0,0,1,0,0,0,1}; if(!n)return r; for(;n>=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<0)t2+=k; t1=pos[t2]; if((ll)ns*t2%k!=1||!t1)break; s[sc].len=t1; s[sc].x=pow((mat){0,1,0,1,1,0,0,0,1},t1-1)*(mat){0,1,0,1,1,0,0,-1,1}; ns=(ll)ns*f[t1-1]%k; } mat bfm=(mat){1,0,0,0,1,0,0,0,1},lpm=(mat){1,0,0,0,1,0,0,0,1},ans=(mat){1,0,0,0,1,0,0,0,1}; ll bf=0,lp=0; fo1(i,p2[ns]-1)bf+=s[i].len,bfm*=s[i].x; fo(i,p2[ns],sc-1)lp+=s[i].len,lpm*=s[i].x; if(!lp)lp=1,lpm=(mat){0,1,0,1,1,0,0,0,1}; if(n<bf) { ans*=get(n,1); } else { ans*=bfm;n-=bf; ans*=pow(lpm,n/lp); ans*=get(n%lp,p2[ns]); } int a1=ans.a[0][1]+ans.a[2][1]; while(a1>=p)a1-=p;while(a1<0)a1+=p; printf("%d\n",a1); } ```
BZOJ 4722: 由乃 November 27, 2016 ###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 <= i <= r，a[i] = a[i] \* a[i] \* a[i] % v ，即区间立方 ###Input 第一行三个数n , m , v，意义如题所述 之后一行n个数，表示序列a 之后m行每行三个数opt , l , r，表示操作类型是1还是2，操作的区间是[l , r] ###Output m行，每行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合 ###Sample Input 20 20 152 3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58 2 1 17 2 6 12 1 1 12 2 3 5 2 11 11 2 7 19 2 6 15 1 5 12 1 1 9 1 10 19 2 3 19 2 6 20 2 1 13 2 1 15 2 1 9 1 1 1 2 1 7 2 7 19 2 6 19 2 3 6 ###Sample Output Yuno Yuno Yuno Yuno Yuki ###HINT 总算在bzoj上出题了呀 这下可以安心退役了~ 总共有10组数据 对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度 ###Solution 当某个区间长度大于13一定有解，小于13 bitset乱搞 立方操作树状数组区间加，取数时倍增 ###Code ```c++ #include<bits/stdc++.h> int n,m,v,u,s[100001],p[100001],N[1000][17],i,j,O,l,r,t,T; main() { scanf("%d%d%d",&n,&m,&v); while((1<<u)<=v)u++; for(;i<v;i++) N[i][0]=1ll*i*i*i%v; for(i=1;i<=n;i++) scanf("%d",s+i); for(i=0;i<16;i++) for(j=0;j<v;j++) N[j][i+1]=N[N[j][i]][i]; while(m--) { scanf("%d%d%d",&O,&l,&r); if(O&1) { if(r-l>=u)puts("Yuno"); else { std::bitset<10360> x(1); for(i=l;i<=r;i++) { t=0,T=s[i]; for(j=i;j;j^=j&-j)t+=p[j]; for(j=0;j<17;j++)if((t>>j)&1)T=N[T][j]; if((x&(x<<T+1)).any()) { puts("Yuno"); goto Y; } x|=x<<T+1; } puts("Yuki"); Y:; } } else { for(i=l;i<=n;i+=i&-i)p[i]++; for(i=r+1;i<=n;i+=i&-i)p[i]--; } } } ```
BZOJ 3038: 上帝造题的七分钟2 November 9, 2016 ###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<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)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<<1]+s[x<<1|1]; ma[x]=max(ma[x<<1],ma[x<<1|1]); } void modify(int x,int l,int r,int ql,int qr) { if(ma[x]<=1)return; if(x&t) { ma[x]=sqrt(ma[x]); s[x]=ma[x]; return; } int q=(l+r)>>1; if(ql<q)modify(x<<1,l,q,ql,min(q,qr)); if(qr>q)modify(x<<1|1,q,r,max(q,ql),qr); up(x); } int main() { int m; scanf("%d",&n); while(t<n+2)t<<=1; for(int i=1;i<=n;i++) scanf("%lld",ma+i+t),s[i+t]=ma[i+t]; for(int i=t-1;i;i--) up(i); scanf("%d",&m); while(m--) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if(x>y)std::swap(x,y); if(opt==0) { modify(1,1,t,x,y+1); } else { x=x+t-1,y=y+t+1; ll ans=0; while(x^y^1) { if(~x&1)ans+=s[x^1]; if(y&1)ans+=s[y^1]; x>>=1,y>>=1; } printf("%lld\n",ans); } } } ```