답안 #19249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19249 2016-02-23T02:06:49 Z kaTkaHr 악수 (kriii4_D) C++14
0 / 100
0 ms 1628 KB
#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 105, MM = 1000000007;

ll rv(ll A){
	ll R = 1, B = MM-2;
	while(B){
		if( B&1 ) R = R * A % MM;
		A = A * A % MM; B /= 2;
	}
	return R;
}

struct frac{
	ll A, B;
	frac(ll a, ll b){
		A = (a%MM+MM) % MM;
		B = (b%MM+MM) % MM;
	}
	frac(){A = 0, B = 1;}
	frac operator+ (const frac &l)const{
		return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
	}
	frac operator*(const frac &l)const{
		return frac(A*l.A % MM, B*l.B % MM);
	}
	frac operator/(const frac &l)const{
		return frac(A*l.B % MM, B*l.A % MM);
	}
	frac operator- (const frac &l)const{
		return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
	}
	ll v(){ return A * rv(B) % MM; }
};

int ans = 0, N;
map<vector<int>, frac> L[900];

frac Solve(vector<int> &D, int T)
{
	if( L[T].find(D) != L[T].end() ) return L[T][D];
	vector<int> E;

	int tot = 0;
	for(int c : D) tot += c * (c-1) / 2;

	frac ans = frac(0, 1);
	if( tot > T ) ans = Solve(D, T+1) * frac(T-tot, N*(N-1)/2 - T);
	for(int i = 0; i < D.size(); i++){
		for(int j = i+1; j < D.size(); j++){
			E.clear();
			for(int k = 0; k < D.size(); k++){
				if( k == i ) E.push_back(D[i] + D[j]);
				else if( k == j );
				else E.push_back(D[k]);
			}
			sort(E.begin(), E.end());
			ans = ans + Solve(E, T+1) * frac(D[i] * D[j], N*(N-1)/2 - T);
		}
	}
	ans = ans + frac(1, 1);
	return L[T][D] = ans;
}

int main()
{
	scanf("%d", &N);
	vector<int> D;
	D.push_back(N);
	for(int i = 0; i < N*N; i++) L[i][D] = frac(0, 1);
	D.clear();
	for(int i = 1; i <= N; i++) D.push_back(1);
	
	frac ans = Solve(D, 0);
	printf("%lld\n", ans.v());
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1628 KB Output is correct
2 Correct 0 ms 1628 KB Output is correct
3 Correct 0 ms 1628 KB Output is correct
4 Incorrect 0 ms 1628 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -