| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19926 |
2016-02-25T07:20:02 Z |
tonyjjw |
악수 (kriii4_D) |
C++14 |
|
669 ms |
66740 KB |
//*
#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;
}
//*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
66740 KB |
Output is correct |
| 2 |
Correct |
11 ms |
66740 KB |
Output is correct |
| 3 |
Correct |
4 ms |
66740 KB |
Output is correct |
| 4 |
Correct |
12 ms |
66740 KB |
Output is correct |
| 5 |
Correct |
8 ms |
66740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
66740 KB |
Output is correct |
| 2 |
Correct |
3 ms |
66740 KB |
Output is correct |
| 3 |
Correct |
10 ms |
66740 KB |
Output is correct |
| 4 |
Correct |
12 ms |
66740 KB |
Output is correct |
| 5 |
Correct |
0 ms |
66740 KB |
Output is correct |
| 6 |
Correct |
8 ms |
66740 KB |
Output is correct |
| 7 |
Correct |
20 ms |
66740 KB |
Output is correct |
| 8 |
Correct |
17 ms |
66740 KB |
Output is correct |
| 9 |
Correct |
13 ms |
66740 KB |
Output is correct |
| 10 |
Correct |
13 ms |
66740 KB |
Output is correct |
| 11 |
Correct |
19 ms |
66740 KB |
Output is correct |
| 12 |
Correct |
16 ms |
66740 KB |
Output is correct |
| 13 |
Correct |
25 ms |
66740 KB |
Output is correct |
| 14 |
Correct |
28 ms |
66740 KB |
Output is correct |
| 15 |
Correct |
26 ms |
66740 KB |
Output is correct |
| 16 |
Correct |
30 ms |
66740 KB |
Output is correct |
| 17 |
Correct |
30 ms |
66740 KB |
Output is correct |
| 18 |
Correct |
29 ms |
66740 KB |
Output is correct |
| 19 |
Correct |
51 ms |
66740 KB |
Output is correct |
| 20 |
Correct |
51 ms |
66740 KB |
Output is correct |
| 21 |
Correct |
70 ms |
66740 KB |
Output is correct |
| 22 |
Correct |
71 ms |
66740 KB |
Output is correct |
| 23 |
Correct |
97 ms |
66740 KB |
Output is correct |
| 24 |
Correct |
107 ms |
66740 KB |
Output is correct |
| 25 |
Correct |
133 ms |
66740 KB |
Output is correct |
| 26 |
Correct |
139 ms |
66740 KB |
Output is correct |
| 27 |
Correct |
188 ms |
66740 KB |
Output is correct |
| 28 |
Correct |
203 ms |
66740 KB |
Output is correct |
| 29 |
Correct |
255 ms |
66740 KB |
Output is correct |
| 30 |
Correct |
302 ms |
66740 KB |
Output is correct |
| 31 |
Correct |
356 ms |
66740 KB |
Output is correct |
| 32 |
Correct |
421 ms |
66740 KB |
Output is correct |
| 33 |
Correct |
492 ms |
66740 KB |
Output is correct |
| 34 |
Correct |
569 ms |
66740 KB |
Output is correct |
| 35 |
Correct |
669 ms |
66740 KB |
Output is correct |
