#UVa:10105-Polynomial Coefficients

根據二項式定理可以求出解。

公式是C(n,n1)*C(n-n1,n2)*C(n-n1-n2,n3)*...*C(n-n1-n2-n3-...-n(k-1), nk),化簡可得n!/(n1!*n2!*n3!*...*nk!)

Ex. (x1+x2+x3+x4)^5 = (x1+x2+x3+x4)*(x1+x2+x3+x4)*(x1+x2+x3+x4)*(x1+x2+x3+x4)*(x1+x2+x3+x4)

相乘時,最後出現的每一項就好像是從這五個一樣的式子中的四個變數,各取一個出來相乘。

要知道x1*x2*x3^3這項的可能性,可能是第一個(x1+x2+x3+x4)中取x1,第二個(x1+x2+x3+x4)中取x2,第三、四、五個(x1+x2+x3+x4)中取x3,把取出來的相乘起來。也有可能是第一個(x1+x2+x3+x4)中取x2,第三個(x1+x2+x3+x4)中取x1,第二、四、五個(x1+x2+x3+x4)中取x3,把取出來的相乘起來。

而所有的可能性就是:C(5,1)*C(4,1)*C(3,3) (意思如同:[取x1,從五個(x1+x2+x3+x4)裡面取一個]*[取x2,從剩下四個(x1+x2+x3+x4)裡面取一個]*[取x3,從剩下三個(x1+x2+x3+x4)裡面取三個]) 而所有乘出來的同樣的項,最後會加起來,所以所有的可能性就是係數,即可得解。

C++(0.016)

/*******************************************************/
/* UVa 10105 Polynomial Coefficients                   */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2012/04/20                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  int n, k, power;
  long long answer;
  while( scanf( "%d%d", &n, &k ) != EOF ){
    answer = 1;
    for( int i = n ; i >= 1 ; i-- ) answer *= i;
    for( int i = 0 ; i < k ; i++ ){
      scanf( "%d", &power );
      for( int j = power ; j >= 1 ; j-- ) answer /= j;
    }
    printf( "%lld\n", answer );
  }
  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料