BZOJ1041: [HAOI2008]圆上的整点 September 18, 2016 ###Description 求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。 ###Input 只有一个正整数n,n<=2000 000 000 ###Output 整点个数 ###Sample Input 4 ###Sample Output 4 ###Solution 只考虑x,y均大于0的情况 首先，暴力枚举肯定是O(n)的，T 对于勾股数有一个结论，就是如果$$x^2+y^2=n^2$$，那么$$x=t(a^2-b^2),y=2tab,n=t(a^2+b^2)$$ 那么我们可以枚举t，显然，只需要枚举n的每个质因数是否在t中就可以了（t中不需要有重复质因子） 枚举t后，需要将n/t写成a^2+b^2的形式，枚举a从1到sqrt(n/t)，时间复杂度O(sqrt(n/t)) 注意去掉重复的a,b，用map实现即可 总时间复杂度应该是根号乘log吧。。 <del>这显然不是正解，不过跑的还是挺快的</del> ###Code ```c++ #include<cstdio> #include<algorithm> #include<cmath> #include<map> std::map<int,bool> f; #define pmax 65536 int prime[10000],pm,x[10],y[10],cc,ans=0,n; bool np[pmax+1]; inline int solve(int nn) { int ans=0; for(int i=sqrt(nn);i>0;i--) { int a=nn-i*i,b=sqrt(nn-i*i); if(b*b==a) { int c=2*b*i,d=std::abs(b*b-i*i); if(!(c&&d))continue; if(!(f[c*(n/nn)]||f[d*(n/nn)])) { f[c*(n/nn)]=f[d*(n/nn)]=1; ans+=8; } } } return ans; } void dfs(int id,int nn) { if(id==cc) { ans+=solve(n/nn); return; } dfs(id+1,nn); dfs(id+1,nn*x[id]); } int main() { for(int i=2;i<=pmax;i++) { if(!np[i])prime[pm++]=i; for(int j=0;j<pm&&i*prime[j]<=pmax;j++) { np[i*prime[j]]=1; if(i%prime[j]==0)break; } } int m; scanf("%d",&n); if(n==0) { printf("1\n"); return 0; } m=n; for(int i=0;i<pm;i++) if(n%prime[i]==0) { x[cc]=prime[i]; while(n%prime[i]==0)n/=prime[i],y[cc]++; cc++; } if(n>1)x[cc++]=n; n=m; dfs(0,1); printf("%d\n",ans+4); return 0; } ```
BZOJ 1798: [Ahoi2009]Seq 维护序列 September 15, 2016 ###Description 老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。 ###Input 第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。 ###Output 对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。 ###Sample Input 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 ###Sample Output 2 35 8 ###Solution 很显然，这是一道线段树区间修改+区间查询的裸题，每个节点存两个tag，分别表示乘多少，加多少，对于加的操作直接处理，乘的操作两个tag都乘 ###Code ```c++ #include<cstdio> #define LL long long int seg[270000],t=1,f=0,t1[270000],t2[270000]={0},p,ys[270000]; bool tag[270000]; inline int se(int x) { if(tag[x]) return ((LL)seg[x]*t1[x]+(LL)t2[x]*ys[x])%p; else return seg[x]; } inline void pd(int x) { if(tag[x]) { t1[x<<1]=(LL)t1[x<<1]*t1[x]%p,t2[x<<1]=((LL)t2[x<<1]*t1[x]+t2[x])%p; t1[x<<1|1]=(LL)t1[x<<1|1]*t1[x]%p,t2[x<<1|1]=((LL)t2[x<<1|1]*t1[x]+t2[x])%p; tag[x<<1]=tag[x<<1|1]=1; seg[x]=se(x); tag[x]=0,t1[x]=1,t2[x]=0; } } inline void up(int x) { if(!tag[x])seg[x]=(se(x<<1)+se(x<<1|1))%p; } int main() { int n,m; scanf("%d%d",&n,&p); while(t<n+2)t<<=1,f++; for(int i=0;i<t+t;i++)t1[i]=1; for(int i=1;i<=n;i++) { scanf("%d",seg+i+t); ys[i+t]=1; } for(int i=t-1;i>0;i--)seg[i]=(seg[i<<1]+seg[i<<1|1])%p,ys[i]=ys[i<<1]+ys[i<<1|1]; scanf("%d",&m); while(m--) { int a,b,c,ff; scanf("%d",&ff); if(ff==3) { scanf("%d%d",&a,&b); int l=a+t-1,r=b+t+1,ll,rr; LL ans=0; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)ans+=se(ll^1); if((rr&1)==1)ans+=se(rr^1); } } printf("%d\n",(int)(ans%p)); } else if(ff==2) { scanf("%d%d%d",&a,&b,&c); int l=a+t-1,r=b+t+1,ll,rr; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)t2[ll^1]=(t2[ll^1]+c)%p,tag[ll^1]=1; if((rr&1)==1)t2[rr^1]=(t2[rr^1]+c)%p,tag[rr^1]=1; } } for(;l;l>>=1,r>>=1) up(l>>1),up(r>>1); } else { scanf("%d%d%d",&a,&b,&c); c%=p; int l=a+t-1,r=b+t+1,ll,rr; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)t1[ll^1]=(LL)t1[ll^1]*c%p,t2[ll^1]=(LL)t2[ll^1]*c%p,tag[ll^1]=1; if((rr&1)==1)t1[rr^1]=(LL)t1[rr^1]*c%p,t2[rr^1]=(LL)t2[rr^1]*c%p,tag[rr^1]=1; } } for(;l;l>>=1,r>>=1) up(l>>1),up(r>>1); } } return 0; } ``` 这个也可以当成zkw线段树区间修改的模板。。
BZOJ 1407: [Noi2002]Savage September 14, 2016 ###Description ![1407.jpg][1] ###Input 第1行为一个整数N(1<=N<=15)，即野人的数目。 第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。 (1<=Ci,Pi<=100, 0<=Li<=10^6) ###Output 仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。 ###Sample Input 3 1 3 4 2 7 3 3 2 1 ###Sample Output 6 ###Solution 枚举m，每次枚举两个野人，将他们的ci,pi相减，记为c,p，那么如果有一个k在他们的年龄范围内，且c+pk模m等于0，则这个m不能取，k的最小值可以用扩展欧几里得求出 预处理每两个野人的ci,pi之差，li的最小值，可以优化时间 ###Code ```c++ #include<cstdio> int n,c[15],p[15],l[15],c2[105],p2[105],l2[105],n2=0; inline int min(int a,int b) { if(a<b)return a;else return b; } inline int max(int a,int b) { if(a>b)return a;else return b; } int sol,gcd; void exgcd(int a,int b,int &x,int &y) { if(!b) { x=sol/a;y=0; gcd=a; return; } exgcd(b,a%b,y,x); y-=x*(a/b); } inline int safeexgcd(int a,int b,int &x,int &y) { if(a<b)exgcd(b,a,y,x);else exgcd(a,b,x,y); } int main() { int maxc=0; scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d%d%d",c+i,p+i,l+i),maxc=max(c[i],maxc); for(int i=0;i<n;i++) for(int j=0;j<i;j++) { c2[n2]=c[i]-c[j]; p2[n2]=p[i]-p[j]; l2[n2]=min(l[i],l[j]); n2++; } for(int i=maxc;1;i++) { bool flag=true; int x,y; for(int j=0;j<n2;j++) { sol=-c2[j]; safeexgcd(p2[j],i,x,y); if(p2[j]*x+i*y!=sol)continue; int tmp=i/gcd; x%=tmp; if(x<0)x+=tmp; if(x<=l2[j]) { flag=false; break; } } if(flag) { printf("%d\n",i); return 0; } } } ``` 另外随便写的代码就第4了 ![puh.png][2] [1]: /usr/uploads/2016/09/2556788862.jpg [2]: /usr/uploads/2016/09/909201119.png
BZOJ 1265: [AHOI2006]斐波卡契的兔子 September 13, 2016 ###Description 卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在m个月后有k对兔子，以便分给他们的好友，他的愿望是否能够实现呢？ [任务] 编写一个程序：从输入文件中读入输入信息；计算m个月后卡卡将有多少对兔子，设之为P；计算如果m个月后卡卡要拥有至少k对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为Q；将结果输出至输出文件。 ###Input 输入文件的第一行有4个正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。 ###Output 你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。 ###Sample Input 0 1 1 10 10000 ###Sample Output 89 113 ###HINT 0 <= a <= b <= c <= 100, 1 <= m <= 3 000, 1 <= k <= 10^6000 ###Solution 我们用x,y,z表示一个月、两个月、三个月及以上的兔子，那么每次x=ax+by+cz,y=x,z=y+z就可以求出p，而q就是k/p向上取整 k/p可以用p,2p,4p,...,(2^t)p去求 然而为什么AC的人这么少呢。。 ###Code ```c++ #include<bits/stdc++.h> #define gm 1000 #define cas 10000000 #define max2 20050 int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3; int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm]; char tmp[10000]; inline void print(int *x,int xl) { printf("%d",x[xl-1]); for(int i=xl-2;i>=0;i--)printf("%07d",x[i]); } inline int max(int a,int b) { if(a>b)return a;else return b; } inline void add(int *x,int *y,int &xl,int yl) { int ll=max(xl,yl); for(int i=0;i<ll;i++) { x[i]+=y[i]; if(x[i]>=cas)x[i]-=cas,x[i+1]++; } if(x[ll])xl=ll+1;else xl=ll; } inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl) { zl=max(xl,yl); z[0]=0; for(int i=0;i<zl;i++) { z[i]+=x[i]+y[i]; if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0; } if(z[zl])zl++; } inline void multo(int *x,int y,int *z,int xl,int &zl) { z[0]=0; for(int i=0;i<xl;i++) { z[i]+=x[i]*y; z[i+1]=z[i]/cas; z[i]%=cas; } if(z[xl])zl=xl+1;else zl=xl; } inline bool larger(int *x,int *y,int xl,int yl) { if(xl>yl)return true; if(xl<yl)return false; for(int i=max(xl,yl)-1;i>=0;i--) { if(x[i]>y[i])return true; if(x[i]<y[i])return false; } return false; } inline void dec(int *x,int *y,int &xl,int yl) { for(int i=0;i<xl;i++) { x[i]-=y[i]; while(x[i]<0)x[i]+=cas,x[i+1]--; } while(xl&&!x[xl-1])xl--; } int main() { al=1,bl=0,cl=0; a[0]=1; scanf("%d%d%d%d",&aa,&bb,&cc,&m); scanf("%s",tmp); int tml=strlen(tmp),tmp2=1; std::reverse(tmp,tmp+tml); kl=(tml+6)/7; for(int i=0;i<tml;i++) { if(i%7==0)tmp2=1; k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2; tmp2*=10; } for(int i=0;i<m;i++) { multo(a,aa,r1,al,l1); multo(b,bb,r2,bl,l2); multo(c,cc,r3,cl,l3); add(c,b,cl,bl); memcpy(b,a,al*4); bl=al; addto(r1,r2,a,l1,l2,al); add(a,r3,al,l3); } add(a,b,al,bl); add(a,c,al,cl); print(a,al); printf("\n"); memcpy(f[0],a,al*4); fl[0]=al; tf[0][0]=1; tfl[0]=1; ansl=0; int ma; for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++) { multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]); multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]); } for(int i=ma-1;i>=0;i--) { if(!larger(f[i],k,fl[i],kl)) { dec(k,f[i],kl,fl[i]); add(ans,tf[i],ansl,tfl[i]); } } if(kl) { rrt[0]=1; add(ans,rrt,ansl,1); } print(ans,ansl); printf("\n"); return 0; } ```
BZOJ 1009: [HNOI2008]GT考试 September 9, 2016 ###Description 阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0 ###Input 第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000 ###Output 阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果. ###Sample Input 4 3 100 111 ###Sample Output 81 ###Solution 我们把不吉利的数字用s表示，用f[i][j]表示n[i]匹配到s[j]的情况数，则可以用一个转移矩阵a通过f[i-1][j]求出f[i][j] a[i][j]表示在s中匹配了i位时，在后面添数，有多少种情况匹配到j位，也就是指s的前i位后面添数后最长的公共前后缀长度为j的情况数 kmp预处理，然后对于每个i，枚举添加的数，再仿照kmp进行处理，即可求出转移矩阵 矩阵快速幂优化就可以过了，时间复杂度$$O(logN*M^3)$$ ###Code ```c++ #include<cstdio> struct _matrix { int s[21][21],a,b; _matrix() { for(int i=0;i<21;i++) for(int j=0;j<21;j++) s[i][j]=0; } }temp; int mod; void mul(_matrix &x,_matrix y) { for(int i=0;i<x.a;i++) for(int j=0;j<y.b;j++) { temp.s[i][j]=0; for(int k=0;k<x.b;k++) temp.s[i][j]+=x.s[i][k]*y.s[k][j]; temp.s[i][j]%=mod; } temp.a=x.a; temp.b=y.b; x=temp; } int m[21],n,f[21]; int main() { int mm; scanf("%d%d%d",&n,&mm,&mod); char t[20]; scanf("%s",t); for(int i=0;i<mm;i++)m[i+1]=t[i]-48; f[1]=0; for(int i=2;i<=mm;i++) { int t=i-1; while(t!=0&&m[f[t]+1]!=m[i])t=f[t]; if(t==0) { if(m[1]==m[i]) f[i]=1; else f[i]=0; } else { f[i]=f[t]+1; } } _matrix a; a.a=mm+1; a.b=mm+1; a.s[0][0]=9,a.s[0][1]=1; for(int i=1;i<mm;i++) { for(int j=0;j<10;j++) { if(m[i+1]==j) { a.s[i][i+1]++; continue; } int t=i; while(t!=0&&m[f[t]+1]!=j)t=f[t]; if(t==0) { if(m[1]==j) a.s[i][t+1]++; else a.s[i][0]++; } else a.s[i][f[t]+1]++; } } _matrix b; b.a=1; b.b=mm+1; b.s[0][0]=9; b.s[0][1]=1; int ans=0,to=n-1,no=1; while(no<to) { if(to&no)mul(b,a); mul(a,a); no<<=1; } for(int i=0;i<mm;i++)ans+=b.s[0][i]; printf("%d\n",ans%mod); return 0; } ```
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