CQUPT第十三届ACM网赛 C 高次OSU题解

CQUPT第十三届ACM网赛 C 高次OSU题解

输入样例:

3 3

0.5 0.5 0.5

输出样例:

6.0 (保留一位小数) 

代码：

#include

using namespace std;

double mem[15][100005];
double pi[100005];


int C( int a  , int b ){
	
	int sum_1 = 1;
	int sum_2 = 1;
	
	for ( int k = 0 ; k <  b ; k++ )	sum_1*=a--;
	
	for ( int k = 1 ; k <= b ; k++ )	sum_2*=k;
	
	return sum_1/sum_2; 
	
}

int main(){
	
	int n,k;
	cin>>n>>k;
	
	for ( int q = 1 ; q <= n ; q++ ){
		
			cin>>pi[q];
			
			for ( int a = 1 ; a < k ; a++ ){//a记录a次方，存入mem[a]; 
			
				mem[a][q] = mem[a][q-1] + 1;
				
				for ( int p = 1 ; p <= a - 1; p++ )
					mem[a][q] += C( a , p )*mem[a-p][q-1];
							
				mem[a][q]*=pi[q];
			}
			
			mem[k][q] = 1;
			for ( int p = 1 ; p <= k - 1; p++ )
				mem[k][q] += C( k , p )*mem[k-p][q-1];
			mem[k][q] *= pi[q];
			
			mem[k][q] += mem[k][q-1];
			
	}
	
	printf("%.1lfn",mem[k][n]);
	
}