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); } } } ```
BZOJ 2656: [Zjoi2012]数列(sequence) October 21, 2016 ###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<=20,N<=10^100 ###Solution 首先手推几个较小的值，可以发现当i为奇数时，递归算几次A(i)，会产生一些相同的值 那么直接记忆化就行了 至于证明，我也不会（从二进制的角度考虑的话，似乎大概就logn种值） ###Code ```c++ #include<cstdio> #include<cstring> #include<tr1/unordered_map> #define bas 1000000000 #define rep(a,b) if(a<(b))a=(b) struct hjd { int a[20],len; hjd(){ len=0; memset(a,0,sizeof(a)); } hjd(const hjd &x) { len=x.len; memset(a,0,sizeof(a)); for(int i=0;i<len;i++)a[i]=x.a[i]; } hjd(int x){ len=1; memset(a,0,sizeof(a)); a[0]=x; } bool operator ==(const hjd &x)const { if(len^x.len)return 0; for(int i=0;i<len;i++) if(a[i]^x.a[i])return 0; return 1; } inline void div2() { for(int i=len-1;i>0;i--) { if(a[i]&1)a[i-1]+=bas; a[i]>>=1; } a[0]>>=1; if(!a[len-1])len--; } inline void plus(const hjd &x) { rep(len,x.len); for(int i=0;i<len;i++) { a[i]+=x.a[i]; if(a[i]>bas)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<x.len;i++) ans^=x.a[i]; return ans; } }; std::tr1::unordered_map<hjd,hjd,hjd_hash> s; int aaa=0; hjd calc(hjd x) { hjd ret; if(!x.len)return ret; while((~x.a[0]&1)&&(x.len!=1||x.a[0]!=1))x.div2();//除去2 if(s.find(x)!=s.end())return s[x];//记忆化 hjd y=x; x.div2(); ret=calc(x); x.plus(1); ret.plus(calc(x));//计算A(x) s[y]=ret; return ret; } char buf[200]; int main() { s[1]=1; int T,n,uu[9],y=1; for(int i=0;i<9;i++) uu[i]=y,y*=10; scanf("%d",&T); while(T--) { s.clear(); s[1]=1; scanf("%s",buf); n=strlen(buf); hjd tmp; for(int i=n-1,j=0,ll=1;i>=0;i--)//输入，倒序 { tmp.len=ll; tmp.a[ll-1]+=(buf[i]-'0')*uu[j]; j++; if(j==9)j=0,ll++; } hjd t2=calc(tmp); if(!t2.len) printf("0\n"); else { t2.print(); } } } ``` [1]: /usr/uploads/2016/10/1978638953.jpg
BZOJ 1089: [SCOI2003]严格n元树 September 8, 2016 ###Description 如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图： ![1.jpg][1] 给出n, d，编程数出深度为d的n元树数目。 ###Input 仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16) ###Output 仅包含一个数，即深度为d的n元树的数目。 ###Sample Input 【样例输入1】 2 2 【样例输入2】 2 3 【样例输入3】 3 5 ###Sample Output 【样例输出1】 3 【样例输出2】 21 【样例输出2】 58871587162270592645034001 ###Solution 我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1) 当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1 ###Code ```c++ #include<cstdio> #include<memory.h> #include<cstring> #define maxnum 100 #define cas 1000000000 int a[maxnum],b[maxnum],t[maxnum],al=1,bl; inline void mul() { memset(t,0,(al+bl+1)*4); for(int i=0;i<al;i++) for(int j=0;j<bl;j++) { long long f=(long long)a[i]*b[j]; t[i+j]+=f%cas; if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++; t[i+j+1]+=f/cas; if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++; } if(t[al+bl-1])al=al+bl;else al=al+bl-1; memcpy(a,t,al*4); } inline void print(int *a) { printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n"); } int main() { int n,d; scanf("%d%d",&n,&d); a[0]=1; while(d--) { memcpy(b,a,al*4); bl=al; for(int i=1;i<n;i++)mul(); a[0]++; for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++; if(a[al])al++; } for(int i=0;i<bl;i++)a[i]-=b[i]; for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--; if(!a[al-1])al--; print(a); printf("\n"); return 0; } ``` [1]: /usr/uploads/2016/09/1813884886.jpg
BZOJ 1002: [FJOI2007]轮状病毒 September 7, 2016 ###Description 轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 ![bzoj1002.p1.png][1] N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示 ![bzoj1002.p2.png][2] 现给定n(N<=100)，编程计算有多少个不同的n轮状病毒 ###Input 第一行有1个正整数n ###Output 计算出的不同的n轮状病毒数输出 ###Sample Input 3 ###Sample Output 16 ###Solution 这道题的正解是基尔霍夫矩阵，推出f[i]=f[i-1]*3-f[i-2]+2，然而我这等蒟蒻肯定是不知道怎么证的 下面是我的做法： 首先去掉外面的某条边，图就变成了类似于这样的结构： ![bzoj1002-1.png][3] 可行解就类似于下图： ![bzoj1002-2.png][4] 我们将未与中心节点相连的点标0，相连的标1，删去的边也标1，每个解就变成了一个01串 假设某个解最外面一共去掉k条边，那么这个01串长度为n+k-1，共有2k-1个1，而由于向上的边与删去的边交替出现，每个解一定与每个01串一一对应，所以最外层去掉k条边时，解的个数为 $$C(n+k-1,k\cdot 2-1)$$。 由于固定了某条边必须去掉，这里只求出了总情况数了k/n，所以还需要乘上n/k，最后的结果就是这样的： $$\sum_k^n C(n+k-1,k\cdot 2-1)\cdot\frac{n}{k}$$ 考虑到高精度大约要O(n)，时间复杂度O(n^3) 记录上一个 $$C(n+k-1,k\cdot 2-1)$$，可以优化到O(n^2) <del>然而这种数据范围为什么不打表。。</del> ###Code ```c++ #include<cstdio> #define cas 10000000 #define maxnum 100 int x[maxnum],y[maxnum],tmp[maxnum+1]; inline void mul(int a) { tmp[0]=0; for(int i=0;i<maxnum;i++) { y[i]*=a; y[i]+=tmp[i]; tmp[i+1]=y[i]/cas; y[i]%=cas; } } inline void div(int a) { for(int i=maxnum-1;i>=0;i--) { if(i)y[i-1]+=y[i]%a*cas; y[i]/=a; } } inline void c(int a,int b) { if(b>a/2)b=a-b; for(int i=0;i<maxnum;i++)y[i]=0; y[0]=1; for(int i=a;i>a-b;i--)mul(i); for(int i=2;i<=b;i++)div(i); } inline void print(int *k) { bool is0=true; for(int i=maxnum-1;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<=n;i++) { c(n+i-1,2*i-1); mul(n); div(i); for(int i=0;i<maxnum;i++) { x[i]+=y[i]; if(x[i]>cas)x[i]-=cas,x[i+1]++; } } print(x); return 0; } ``` [1]: /usr/uploads/2016/09/2454961388.png [2]: /usr/uploads/2016/09/212298548.png [3]: /usr/uploads/2016/09/3955661276.png [4]: /usr/uploads/2016/09/3098156740.png [5]: /usr/uploads/2016/09/1992184554.gif [6]: /usr/uploads/2016/09/1288349390.gif [7]: /usr/uploads/2016/09/1992184554.gif