acm网络赛解题报告

《acm网络赛解题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、HGFHFKKHJKGHLH;KJKLHLKLKHKLHKLHLJK2012.12江西师范大学ACM网络赛解题报告MakebyECJTU_ACM，2012-12-18http://acm.hdu.edu.cn/diy/contest_show.php?cid=18217（比赛已结束，无赛后提交地址）1001、Binomial组合数，整数快速幂乘11002、Factorial大整数31003、Rayrays广度优先搜索bfs61004、这是字符串问题吗？字符串简单题91005、COH模拟题111006、Triangle简单动态规划入门题131007、GCD最大公约数161008、JXNU最短路

2、Dijkstra，floyd171009、Qsortsort函数201010、Tree完全二叉树的三种遍历221001、Binomial组合数，整数快速幂乘题目：ProblemDescription来到大学，小KD发现自己已经忘了高中数学知识了……小KD遇到了麻烦，请作为编程高手的你来解决。小KD遇到的问题是：有一个多项式(ax+by)^k，请求出多项式展开后x^n,y^m项的系数。Input输入数据有多组，每组占一行，每行包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。保证0≤k≤1,000，0≤n,m≤k，且n+m=k，0≤a，b≤5000。Output对于每组输入

3、数据，输出一行，每行包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。SampleInput11312FGKJGLLKGLGJHJGKJGJJGJGHJGJGJKHGFHFKKHJKGHLH;KJKLHLKLKHKLHKLHLJKSampleOutput3分析：(x+y)^3=x^3+3*x^2*y^1+3*x^1*y^2+y^3;二项式系数：1331(x+y)^4=x^4+4*x^3*y^1+6*x^2*y^2+4*x^1*y^3+y^4;二项式系数：14641类推……(ax+by)^3=(ax)^3+3*(ax)^2*(by)^1+3*(ax)^1*(by)^

4、2+(by)^3;类推……所以题目求的系数是：C(k,m)*a^n*b^m(C(n,m)代表组合数，n个里面取m个，结果对mod=10007取模);组合数可以先预处理保存，C(n,m)=C(n-1,m)+C(n-1,m-1);时间复杂度：O(1000^2);a^n,b^n可以直接for循环计算，或者用整数快速幂乘。For循环算的时间复杂度：O(1000);整数快速幂乘:O(log1000=10);因粘贴不当以下的代码缩进是3格，大家要养成缩进4格的习惯。代码：C++语言: jxnu_1001//http://acm.hdu.edu.cn/diy/contest_showproblem.php

5、?pid=1001&cid=18217&hide=0#include#definemaxn1005const int mod = 10007;/*预处理计算组合数，算到1000即可，题目要求取模， 所以边算边取模，不会超过2^31（越界）*/int c[maxn][maxn];void Init(){  c[0][0]= 1;  for(int i=1; i

6、or(int j=1; j>= 1;  }  return r;}int main(){  int a, b, k, n, m;  Ini

7、t(); ///在所有的询问之前先算好，只算一次；  while(scanf("%d%d%d%d%d", &a, &b, &k, &n, &m)!=EOF){    printf("%d", c[k][m] * (( Pow(a, n) * Pow(b, m))%mod ) %mod );    //上面只是理论分析的代码，没有ac，但个人觉得没问题；    //取模要边乘边取；  }}1002、Fact