php做动漫网站公司网站建设招标文件范本

php做动漫网站,公司网站建设招标文件范本,西安英文网站制作,免费房地产网站模板【题目链接】 ybt 1648#xff1a;【例 1】「NOIP2011」计算系数 ybt 1866#xff1a;【11NOIP提高组】计算系数 洛谷 P1313 [NOIP 2011 提高组] 计算系数 ybt 1648没有指明 k k k的范围#xff0c;在ybt 1866#xff0c; 洛谷P1313中都以指明 k ≤ 1000 k\le1000 k≤1000…【题目链接】ybt 1648【例 1】「NOIP2011」计算系数ybt 1866【11NOIP提高组】计算系数洛谷 P1313 [NOIP 2011 提高组] 计算系数ybt 1648没有指明k kk的范围在ybt 1866 洛谷P1313中都以指明k ≤ 1000 k\le1000k≤1000【题目考点】1. 加法原理与乘法原理加法原理完成一件事的方法有n nn类第i ii类包括m i m_imi​种不同的方法而且这些方法不重合则完成这件事共有N NN种方法满足N m 1 m 2 ⋯ m n Nm_1m_2⋯m_nNm1​m2​⋯mn​。口诀分类相加乘法原理完成一件事需要n nn个步骤其中第i ii个步骤有m i m_imi​种不同的完成方法而且这些步骤互不干扰则完成这件事共有N NN种方法满足N m 1 m 2 ⋯ m n Nm_1m_2⋯m_nNm1​m2​⋯mn​。口诀分步相乘2. 排列组合排列从n nn个不同的元素中取m ( m ≤ n ) m (m≤n)m(m≤n)个元素按照一定顺序排成一列称为从n nn个不同元素中取出m mm个元素的一个排列这样的排列的个数称为排列数记为P n m P_n^mPnm​或A n m A_n^mAnm​。P n n P_n^nPnn​称为n nn个元素的全排列。P n m n ( n − 1 ) . . . ( n − m 1 ) n ! ( n − m ) ! P_n^mn(n-1)...(n-m1)\dfrac{n!}{(n-m)!}Pnm​n(n−1)...(n−m1)(n−m)!n!​第1步从n nn个元素中取出一个元素共n nn种取法。第2步从n − 1 n-1n−1个元素中取出一个元素共n − 1 n-1n−1种取法。…第m mm步从n − m 1 n-m1n−m1个元素中取出一个元素共n − m 1 n-m1n−m1种取法。根据乘法原理有P n m n ( n − 1 ) . . . ( n − m 1 ) P_n^mn(n-1)...(n-m1)Pnm​n(n−1)...(n−m1)组合从n nn个不同的元素中取m ( m ≤ n ) m(m\le n)m(m≤n)个元素组成一个集合称为从n nn个不同元素中取出m mm个元素的一个组合这样的组合的个数称为组合数记为C n m C_n^mCnm​。C n m P n m P m m n ( n − 1 ) . . . ( n − m 1 ) m ( m − 1 ) . . . 1 n ! ( n − m ) ! m ! C_n^m\dfrac{P_n^m}{P_m^m}\dfrac{n(n-1)...(n-m1)}{m(m-1)...1}\dfrac{n!}{(n-m)!m!}Cnm​Pmm​Pnm​​m(m−1)...1n(n−1)...(n−m1)​(n−m)!m!n!​从n nn个元素中取出m mm个元素可以分为两步第一步从n nn个元素中取出m mm个元素的一个组合方案数为C n m C_n^mCnm​第二步将这m mm个元素进行全排列方案数为P m m P_m^mPmm​根据乘法原理有P n m C n m P m m P_n^mC_n^mP_m^mPnm​Cnm​Pmm​因此C n m P n m P m m C_n^m\frac{P_n^m}{P_m^m}Cnm​Pmm​Pnm​​C n m C n n − m C_n^mC_n^{n-m}Cnm​Cnn−m​一般用于简化计算过程。特殊地C n 0 C n n 1 C_n^0C_n^n1Cn0​Cnn​1。当m n mnmn时不存在从n nn个数中取出m mm个数的方案C n m 0 C_n^m0Cnm​0从n nn个元素中取出m mm个元素拿走和在n nn个元素中取出n − m n-mn−m个元素留下的方案数是相同的。杨辉恒等式C n m C n − 1 m C n − 1 m − 1 C_n^mC_{n-1}^{m}C_{n-1}^{m-1}Cnm​Cn−1m​Cn−1m−1​在n nn个元素中存在一个元素x xx。如果不选择x xx那么接下来要在剩下的n − 1 n-1n−1个元素中再选择m mm个元素方案数为C n − 1 m C_{n-1}^{m}Cn−1m​如果选择x xx那么接下来要在剩下的n − 1 n-1n−1个元素中再选择m − 1 m-1m−1个元素方案数为C n − 1 m − 1 C_{n-1}^{m-1}Cn−1m−1​根据加法原理有C n m C n − 1 m C n − 1 m − 1 C_n^mC_{n-1}^{m}C_{n-1}^{m-1}Cnm​Cn−1m​Cn−1m−1​C n m n m C n − 1 m − 1 C_n^m\dfrac{n}{m}C_{n-1}^{m-1}Cnm​mn​Cn−1m−1​C n m n ! ( n − m ) ! m ! n m ( n − 1 ) ! ( n − m ) ! ( m − 1 ) ! n m C n − 1 m − 1 C_n^m\frac{n!}{(n-m)!m!}\frac{n}{m}\frac{(n-1)!}{(n-m)!(m-1)!}\frac{n}{m}C_{n-1}^{m-1}Cnm​(n−m)!m!n!​mn​(n−m)!(m−1)!(n−1)!​mn​Cn−1m−1​2. 二项式定理( a b ) n ∑ i 0 n C n i a i b n − i (ab)^n \sum\limits_{i0}^nC_n^ia^ib^{n-i}(ab)ni0∑n​Cni​aibn−i或( a b ) n C n 0 a 0 b n C n 1 a b n − 1 . . . C n n − 1 a n − 1 b C n n a n b 0 (ab)^nC_n^0a^0b^{n}C_n^1ab^{n-1}...C_n^{n-1}a^{n-1}bC_n^na^nb^{0}(ab)nCn0​a0bnCn1​abn−1...Cnn−1​an−1bCnn​anb0每一个( a b ) (ab)(ab)提供一个a aa或b bb对于a i b n − i a^ib^{n-i}aibn−i项需要在n nn个( a b ) (ab)(ab)中选择i ii个( a b ) (ab)(ab)提供a aa另外n − i n-in−i个( a b ) (ab)(ab)中提供b bb共C n i C_n^iCni​种情况根据加法原理a i b n − i a^ib^{n-i}aibn−i项的系数为C n i C_n^iCni​。【解题思路】设M 10007 M10007M10007可以手写质数判断函数确定M MM为质数。已知n m k nmknmk所以m k − n mk-nmk−n根据二项式定理( a x b y ) k (axby)^k(axby)k的x n y m x^ny^mxnym项为C k n ( a x ) n ( b y ) k − n C k n a n b k − n x n y k − n C k n a n b m x n y m C_k^n(ax)^n(by)^{k-n}C_k^na^nb^{k-n}x^ny^{k-n}C_k^na^nb^mx^ny^mCkn​(ax)n(by)k−nCkn​anbk−nxnyk−nCkn​anbmxnym因此该项的系数为C k n a n b m m o d M C_k^na^nb^m\bmod MCkn​anbmmodM。可以使用快速幂求a n a^nan与b m b^mbm。对于求组合数C k n C_k^nCkn​有以下方法1. 求组合数数组状态定义设二维数组cc[i][j]表示C i j C_i^jCij​。由于k ≤ 1000 k\le 1000k≤1000所以数组的行数列数可以定为1005。初始状态C i 0 1 , i ∈ [ 0 , n ] C_i^01, i\in[0,n]Ci0​1,i∈[0,n]注意包括C 0 0 1 C_0^01C00​1由于结果要对M MM取模我们求出的组合数也对M MM取模。递推关系C i j ≡ C i − 1 j C i − 1 j − 1 ( m o d M ) C_i^j\equiv C_{i-1}^{j}C_{i-1}^{j-1} \pmod MCij​≡Ci−1j​Ci−1j−1​(modM)其中j ∈ [ 1 , i ] j\in[1,i]j∈[1,i]递推求出c数组即可求出C n k C_n^kCnk​。同样可以根据该原理写出记忆化递归算法。该方法求C n m C_n^mCnm​空间复杂度O ( n 2 ) O(n^2)O(n2)时间复杂度预处理O ( n 2 ) O(n^2)O(n2)单次查询O ( 1 ) O(1)O(1)。2. 使用阶乘公式C n m ≡ n ! ( n − m ) ! m ! ( m o d M ) C_n^m\equiv \dfrac{n!}{(n-m)!m!}\pmod MCnm​≡(n−m)!m!n!​(modM)设阶乘数组facfac[i]表示i ! i!i!。先预处理出1 ∼ k 1\sim k1∼k的阶乘。设阶乘模M MM逆元的数组facInvfacInv[i]表示i ! − 1 m o d M i!^{-1}\bmod Mi!−1modM先使用扩展欧几里得算法求出n ! − 1 m o d M n!^{-1}\bmod Mn!−1modM由于M MM是质数也可以使用快速幂求逆元。已知i ! − 1 ≡ ( i 1 ) − 1 ( i 1 ) ( m o d M ) i!^{-1}\equiv (i1)^{-1}(i1)\pmod Mi!−1≡(i1)−1(i1)(modM)而后使用该公式递推求出facInv数组。C n m ≡ n ! ( n − m ) ! m ! ≡ n ! ( n − m ) ! − 1 m ! − 1 ( m o d M ) C_n^m\equiv \dfrac{n!}{(n-m)!m!}\equiv n!(n-m)!^{-1}m!^{-1}\pmod MCnm​≡(n−m)!m!n!​≡n!(n−m)!−1m!−1(modM)fac[n]为n ! n!n!facInv[n-1]为( n − m ) ! − 1 m o d M (n-m)!^{-1}\bmod M(n−m)!−1modMfacInv[m]为m ! − 1 m o d M m!^{-1}\bmod Mm!−1modM可以通过该公式求出C n m C_n^mCnm​该方法求C n m C_n^mCnm​空间复杂度O ( n ) O(n)O(n)时间复杂度预处理O ( n ) O(n)O(n)查询O ( 1 ) O(1)O(1).3. 使用乘除计算公式C n m ≡ n ( n − 1 ) . . . ( n − m 1 ) m ( m − 1 ) . . . 1 ( m o d M ) C_n^m\equiv \dfrac{n(n-1)...(n-m1)}{m(m-1)...1}\pmod MCnm​≡m(m−1)...1n(n−1)...(n−m1)​(modM)先求出m ! m o d M m!\bmod Mm!modM再通过扩展欧几里得算法模数为质数时可用快速幂求出m ! − 1 m o d M m!^{-1}\bmod Mm!−1modM。即C n m ≡ n ( n − 1 ) . . . ( n − m 1 ) m ! − 1 ( m o d M ) C_n^m\equiv n(n-1)...(n-m1)m!^{-1}\pmod MCnm​≡n(n−1)...(n−m1)m!−1(modM)该方法求C n m C_n^mCnm​空间复杂度O ( 1 ) O(1)O(1)时间复杂度O ( m ) O(m)O(m)【题解代码】1. 求组合数数组写法1递推#includebits/stdc.husingnamespacestd;constintN1005,M10007;typedeflonglongLL;LL a,b,k,n,m,c[N][N];//c[i][j]:组合数C(i, j)LLfastPow(LL a,LL b,LL m){LL r1;while(b0){if(b%21)rr*a%m;aa*a%m;b/2;}returnr;}voidinitComb(LL n){for(inti0;in;i)c[i][0]1;for(inti1;in;i)for(intj1;ji;j)c[i][j](c[i-1][j]c[i-1][j-1])%M;}intmain(){cinabknm;initComb(k);coutfastPow(a,n,M)*fastPow(b,m,M)*c[k][n]%M;return0;}写法2记忆化递归#includebits/stdc.husingnamespacestd;constintN1005,M10007;typedeflonglongLL;LL a,b,k,n,m,c[N][N];//c[i][j]:组合数C(i, j)LLfastPow(LL a,LL b,LL m){LL r1;while(b0){if(b%21)rr*a%m;aa*a%m;b/2;}returnr;}LLcomb(LL n,LL m){if(mn)return0;if(m0)return1;if(c[n][m]0)returnc[n][m];returnc[n][m](comb(n-1,m)comb(n-1,m-1))%M;}intmain(){cinabknm;coutfastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}2. 使用阶乘公式#includebits/stdc.husingnamespacestd;constintN1005,M10007;typedeflonglongLL;LL a,b,k,n,m,fac[N],facInv[N];LLfastPow(LL a,LL b,LL m){LL r1;while(b0){if(b%21)rr*a%m;aa*a%m;b/2;}returnr;}voidinitFac(LL n){fac[0]1;for(inti1;in;i)fac[i]fac[i-1]*i%M;//fac[i]i!facInv[n]fastPow(fac[n],M-2,M);for(intin-1;i0;--i)//注意包括0facInv[i]facInv[i1]*(i1)%M;//facInv[i]i!^{-1} mod M}LLcomb(LL n,LL m){if(nm)return0;returnfac[n]*facInv[n-m]%M*facInv[m]%M;}intmain(){cinabknm;initFac(k);coutfastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}3. 使用乘除计算公式#includebits/stdc.husingnamespacestd;constintN1005,M10007;typedeflonglongLL;LL a,b,k,n,m,fac[N],facInv[N];LLfastPow(LL a,LL b,LL m){LL r1;while(b0){if(b%21)rr*a%m;aa*a%m;b/2;}returnr;}LLcomb(LL n,LL m){if(mn)return0;LL fz1,fm1;for(inti1;im;i){fzfz*(n-i1)%M;fmfm*i%M;}returnfz*fastPow(fm,M-2,M)%M;}intmain(){cinabknm;coutfastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}