Submission #19495

#	Time	Username	Problem	Language	Result	Execution time	Memory
19495		kaTkaHr	악수 (kriii4_D)	C++14	100 / 100	2942 ms	34544 KiB

D

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 45, MM = 1000000007;

template<typename T>
T pw(T A, ll B){
  T R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

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):A(A), B(1){}
  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; }
};// */
//*
struct frac{
  ll A;
		frac(ll A):A((A%MM+MM)%MM){}
  frac(ll a, ll b){
			a = (a%MM+MM)%MM;
			b = (b%MM+MM)%MM;
			A = rv(b) * a % MM;
  }
  frac(){A = 0;}
  frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
  }
  frac operator*(const frac &l)const{
			return l.A * A % MM;
  }
  frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
  }
  frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
  }
  ll v(){ return A; }
};// */

frac D[MX][MX*MX], E[MX][MX*MX], C[MX*MX][MX*MX];

int main()
{
	int N, T;
	scanf("%d", &N); T = N*(N-1) / 2;

	C[0][0] = 1;
	for(int i = 1; i <= T || i <= N; i++){
		C[i][0] = 1;
		for(int j = 1; j <= i; j++){
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}

	D[1][0] = E[1][0] = 1;
	for(int i = 2; i <= N; i++){
		for(int x = i-1; x <= i*(i-1)/2; x++){
			for(int k = 1; k <= i-1; k++){
				frac t = 0;
				for(int l = 0; l <= x-1; l++){
					t = t + D[k][l] * D[i-k][x-l-1] * C[x-1][l];
				}
				E[i][x] = E[i][x] + t * C[i-1][k-1] * frac(k*(i-k),1);
			}
			D[i][x] = D[i][x-1] * frac(i*(i-1)/2 - x + 1, 1) + E[i][x];
		}
	}
	frac ans = 0, mul = 1;
	frac tot = 0;
	for(int i = 0; i <= T; i++){
		tot = tot + E[N][i] * mul;
		ans = ans + E[N][i] * i * mul;
		mul = mul * frac(1, T-i);
	}
	printf("%lld\n", ans.v());
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95