Submission #19926

#	Time	Username	Problem	Language	Result	Execution time	Memory
19926		tonyjjw	악수 (kriii4_D)	C++14	100 / 100	669 ms	66740 KiB

D

//*
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <functional>
#define MOD 1000000007
#define MAX 0x3f3f3f3f
#define MAX2 0x3f3f3f3f3f3f3f3fll
#define ERR 1e-10
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
using namespace std;

typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

ll mul_inv(ll a, ll b=MOD)
{
	ll b0=b, t, q;
	ll x0=0, x1=1;
	if(b == 1) return 1;
	while(a > 1)
	{
		q=a/b;
		t=b, b=a%b, a=t;
		t=x0, x0=x1-q*x0, x1=t;
	}
	if(x1 < 0) x1+=b0;
	return x1;
}

ll ncr[2600][2600];
ll d[200][2600];
ll e[200][2600];
ll f[200][2600];
ll fac[2600];

int n;

ll npr(ll n, ll r)
{
	if(r > n) return 0;
	return fac[n]*mul_inv(fac[n-r])%MOD;
}

void addmod(ll &x, ll y)
{
	x+=y, x%=MOD;
}

int main()
{
	int i, j, k;
	cin>>n;
	if(n == 1) return !printf("0");
	for(i=0;i<2600;i++) for(j=0;j<=i;j++) ncr[i][j]=j==0||j==i?1:ncr[i-1][j-1]+ncr[i-1][j], ncr[i][j]%=MOD;
	fac[0]=1;
	for(i=1;i<2600;i++) fac[i]=fac[i-1]*i, fac[i]%=MOD;
	d[1][0]=1;
	e[1][0]=0;
	f[1][0]=1;
	d[2][0]=0;
	e[2][0]=1;
	f[2][0]=1;
	d[2][1]=1;
	e[2][1]=0;
	f[2][1]=1;
	for(i=3;i<=n;i++)
	{
		for(j=0;j<=ncr[i][2];j++)
		{
			f[i][j]=npr(ncr[i][2], j);
			ll xsum=0;
			for(int s=1;s<=i-1;s++)
			{
				ll sum=0;
				for(k=0;k<=j;k++)
				{
					addmod(sum, d[s][k]*f[i-s][j-k]%MOD*ncr[j][k]);
				}
				sum*=ncr[i-1][s-1], sum%=MOD;
				xsum+=sum, xsum%=MOD;
			}
			e[i][j]=xsum;
			d[i][j]=(f[i][j]-xsum)%MOD;
			if(d[i][j] < 0) d[i][j]+=MOD;
		}
	}
	ll ex=0;
	ll tot=fac[ncr[n][2]];
	for(j=1;j<=ncr[n][2];j++)
	{
		ex+=j*(d[n][j]*fac[ncr[n][2]-j]%MOD-d[n][j-1]*fac[ncr[n][2]-(j-1)]%MOD+MOD)%MOD;
		ex%=MOD;
	}
	ex*=mul_inv(tot);
	ex%=MOD;
	cout<<ex;
	return 0;
}
//*/

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