Submission #9119212


Source Code Expand

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10,L=N*N;
const int mod=1e9+7;
inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int fac[L],ifac[L];
inline void init(int n) {
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (re int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int n,k,dp[N][N];

int main() {
    n=read(),k=read(); init(n*k);
    if (k==1) { puts("1"); return 0; }
    for (re int i=1;i<=n;++i) dp[i][0]=1;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=i;++j)
            dp[i][j]=(dp[i-1][j]+1ll*dp[i][j-1]*(n-j+1)%mod*C(n*k-i-(j-1)*(k-1)-1,k-2))%mod;
    printf("%d\n",dp[n][n]);
    return 0;
}

Submission Info

Submission Time
Task F - Leftmost Ball
User M_sea
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 1320 Byte
Status AC
Exec Time 91 ms
Memory 46592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 24
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
Case Name Status Exec Time Memory
0_00.txt AC 2 ms 4352 KB
0_01.txt AC 2 ms 4352 KB
0_02.txt AC 2 ms 4352 KB
0_03.txt AC 91 ms 46592 KB
1_00.txt AC 2 ms 4352 KB
1_01.txt AC 2 ms 4352 KB
1_02.txt AC 2 ms 4352 KB
1_03.txt AC 91 ms 46592 KB
1_04.txt AC 84 ms 46464 KB
1_05.txt AC 87 ms 46464 KB
1_06.txt AC 86 ms 46464 KB
1_07.txt AC 77 ms 46464 KB
1_08.txt AC 77 ms 46464 KB
1_09.txt AC 78 ms 46464 KB
1_10.txt AC 83 ms 46464 KB
1_11.txt AC 80 ms 46464 KB
1_12.txt AC 16 ms 17792 KB
1_13.txt AC 73 ms 44416 KB
1_14.txt AC 3 ms 4864 KB
1_15.txt AC 21 ms 19840 KB
1_16.txt AC 35 ms 28032 KB
1_17.txt AC 60 ms 38272 KB
1_18.txt AC 5 ms 7552 KB
1_19.txt AC 87 ms 46464 KB