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 3884: 上帝与集合的正确用法 October 16, 2016 ###Description 根据一些书上的记载，上帝的一次失败的创世经历是这样的： 第一天， 上帝创造了一个世界的基本元素，称做“元”。 第二天， 上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。 第三天， 上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。 第四天， 上帝创造了新的元素“γ”，“γ”被定义为“β”的集合。显然，一共会有16种不同的“γ”。 如果按照这样下去，上帝创造的第四种元素将会有65536种，第五种元素将会有2^65536种。这将会是一个天文数字。 然而，上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来，因此，日复一日，年复一年，他重复地创造着新的元素…… 然而不久，当上帝创造出最后一种元素“θ”时，他发现这世界的元素实在是太多了，以致于世界的容量不足，无法承受。因此在这一天，上帝毁灭了世界。 至今，上帝仍记得那次失败的创世经历，现在他想问问你，他最后一次创造的元素“θ”一共有多少种？ 上帝觉得这个数字可能过于巨大而无法表示出来，因此你只需要回答这个数对p取模后的值即可。 你可以认为上帝从“α”到“θ”一共创造了10^9次元素，或10^18次，或者干脆∞次。 一句话题意： ![1.png][1] ###Input 接下来T行，每行一个正整数p，代表你需要取模的值 ###Output T行，每行一个正整数，为答案对p取模后的值 ###Sample Input 3 2 3 6 ###Sample Output 0 1 4 ###HINT 对于100%的数据，T<=1000,p<=10^7 ###Solution 首先考虑欧拉定理，如果把这个数设为S，可以发现$$2^S=2^{S\ mod\ \phi(p)}$$ （当p是2的倍数时可以先除去所有2处理） 那么问题就转化为了求$$S\ mod\ \phi(p)$$，同样考虑，最终$$\phi(p)$$会等于1，直接处理即可 由于除了第一次，每次都会除去至少一个2，所以单次时间复杂度为$$O(logp)$$ ###Code ```c++ #include<cstdio> #define pmax 10000000 int prime[1000000],pm,fi[pmax+1],ans[pmax+1]; bool np[pmax+1],ga[pmax+1]; inline int pow(int a,long long t,int mod) { long long p=1,q=a,f=1; for(;f<=t;f<<=1) { if(f&t)p=p*q%mod; q=q*q%mod; } return p; } void exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return; } exgcd(b,a%b,y,x); y-=(a/b)*x; } inline int gen(int x,int t) { if(x==1)return 0; int a,b,p; if(x>t)exgcd(x,t,a,b);else exgcd(t,x,b,a); p=(long long)ans[x]*t%(x*t)*b%(x*t); if(p<0)p+=x*t; return p; } int getans(int x) { int t=1; while(~x&1)x>>=1,t<<=1; if(!ga[x])ga[x]=1,ans[x]=pow(2,1000ll*fi[x]+getans(fi[x]),x); return gen(x,t); } int main() { for(int i=2;i<=pmax;i++) { if(!np[i])prime[pm++]=i,fi[i]=i-1; for(int j=0;j<pm&&i*prime[j]<=pmax;j++) { np[i*prime[j]]=1; if(i%prime[j]) { fi[i*prime[j]]=fi[i]*(prime[j]-1); } else { fi[i*prime[j]]=fi[i]*prime[j]; break; } } } ga[1]=1,ans[1]=0; int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%d\n",getans(n)); } } ``` [1]: /usr/uploads/2016/10/774614809.png
Codeforces 723E.One-Way Reform October 3, 2016 ###Description There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads. The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it. 有一个无向图，n个点，m条边，无自环，无重边，现在要给每个边定方向，使得入度等于出度的点最多 ###Input The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input. Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland. The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities. It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200. Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one. ###Output For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it. In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. ###Example input 2 5 5 2 1 4 5 2 3 1 3 3 5 7 2 3 7 4 2 output 3 1 3 3 5 5 4 3 2 2 1 3 2 4 3 7 ###Solution 将度数为奇的边间连上边，然后每次从任一点出发，走过一条边就定为走的方向，直到回到出发点。当所有边被定向后停止操作 那么对于度数为偶数的边，其入度一定等于出度，输出时去掉新加的边 ###Code ```c++ #include<bits/stdc++.h> struct edge { int to,ne; bool v; }e[50000]; int p[201],em=2,deg[201],n,m; bool ok[50000]; inline void add(int a,int b,bool v) { e[em].to=b,e[em].v=v,e[em].ne=p[a],p[a]=em++; } inline void solve() { scanf("%d%d",&n,&m); em=2; memset(p,0,n*4+4); memset(deg,0,n*4+4); while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b,1); add(b,a,1); deg[a]++; deg[b]++; } int lst=0,ans=n; for(int i=1;i<=n;i++) if(deg[i]&1) { if(lst) add(i,lst,0),add(lst,i,0),deg[i]++,deg[lst]++; else lst=i; ans--; } memset(ok,0,em); lst=1; printf("%d\n",ans); while(1) { while(lst<=n&&!deg[lst])lst++; if(lst>n)break; int k=lst; while(1) { bool f=1; for(int i=p[k];i;i=e[i].ne) if(!ok[i]) { f=0,ok[i]=1,ok[i^1]=1; if(e[i].v)printf("%d %d\n",k,e[i].to); deg[k]--; deg[e[i].to]--; k=e[i].to; break; } if(f)break; } } } int main() { int T; scanf("%d",&T); while(T--)solve(); } ```
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 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