AOJ 0070: Combination of Number Sequences

next_permutation()使って、DP。
重複して数えてるから、重複した回数((10-n)!回)で割ってあげる。本当は重複しないで数えたいところだが、これでもそんなに遅くないので妥協した。

int num[10];
long  fact[10],dp[10][331];//和が331以上になることはない。dp[10][1000]とかでも問題ない

int main(){
	for(int i = 0; i < 10; i++){
		num[i] = i;
	}
	
	do{
		int t = 0;
		for(int i = 0; i < 10; i++){
			t += num[i]*(i+1);
			dp[i][t]++;
		}
	}while(next_permutation(num,num+10));
	
	fact[0] = 1;
	for(int i = 1; i < 10; i++){
		fact[i] = fact[i-1]*i;
	}
	
	int n,s;
	while(cin>>n>>s){
		if(n > 10 || s > 330){
			cout<<0<<endl;
			continue;
		}
		if(n == 0){
			if(s == 0) cout<<1<<endl;
			else cout<<0<<endl;
			continue;
		}
		cout<<dp[n-1][s]/fact[10-n]<<endl;
	}
	return 0;
}