Submission #826808
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
template<lint mod>
struct Int_{
unsigned x;
unsigned mpow(Int_ a,unsigned k){
Int_ res=1;
while(k){
if(k&1) res=res*a;
a=a*a;
k>>=1;
}
return res.x;
}
unsigned inverse(Int_ a){
return mpow(a,mod-2);
}
Int_(): x(0) { }
Int_(long long sig) {
int sigt=sig%mod;
if(sigt<0) sigt+=mod;
x=sigt;
}
unsigned get() const { return (unsigned)x; }
Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; }
Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; }
Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; }
Int_ &operator=(Int_ that) { x=that.x; return *this;}
Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;}
bool operator==(Int_ that) const { return x==that.x; }
bool operator!=(Int_ that) const { return x!=that.x; }
Int_ operator-() const { return Int_(0)-Int_(*this);}
Int_ operator+(Int_ that) const { return Int_(*this) += that; }
Int_ operator-(Int_ that) const { return Int_(*this) -= that; }
Int_ operator*(Int_ that) const { return Int_(*this) *= that; }
Int_ operator/(Int_ that) const { return Int_(*this) /= that; }
};
namespace std{
template<lint mod>
ostream &operator <<(ostream& out,const Int_<mod>& a){
out<<a.get();
return out;
}
template<lint mod>
istream &operator >>(istream& in,Int_<mod>& a){
in>>a.x;
return in;
}
};
typedef Int_<1000000007> Int;
//const int INF=5e8;
int n,k;
Int dp[2005][2005];
Int fact[4000005],inv[4000005];
Int C(int a,int b){
return fact[a]*inv[b]*inv[a-b];
}
int main(){
const int M=4000000;
fact[0]=1;
REP(i,M) fact[i+1]=fact[i]*(i+1);
Int one=1;
REP(i,M) inv[i]=one/fact[i];
cin>>n>>k;
if(n==1 || k==1){
puts("1");
return 0;
}
dp[0][0]=1;
REP(i,n+1) REP(j,n+1) if(dp[i][j].x && i>=j){
if(i<n){
dp[i+1][j]+=dp[i][j];
}
if(j<n){
dp[i][j+1]+=dp[i][j]*C((n-j)*(k-1)+(n-i)-1,k-2)*(n-j);
}
}
Int res=dp[n][n];
cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Leftmost Ball |
User |
hogloid |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
3157 Byte |
Status |
AC |
Exec Time |
1231 ms |
Memory |
47232 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
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 |
977 ms |
47232 KB |
0_01.txt |
AC |
988 ms |
47232 KB |
0_02.txt |
AC |
978 ms |
47232 KB |
0_03.txt |
AC |
1205 ms |
47232 KB |
1_00.txt |
AC |
988 ms |
47232 KB |
1_01.txt |
AC |
978 ms |
47232 KB |
1_02.txt |
AC |
988 ms |
47232 KB |
1_03.txt |
AC |
1208 ms |
47232 KB |
1_04.txt |
AC |
1208 ms |
47232 KB |
1_05.txt |
AC |
1231 ms |
47232 KB |
1_06.txt |
AC |
1203 ms |
47232 KB |
1_07.txt |
AC |
1187 ms |
47232 KB |
1_08.txt |
AC |
1183 ms |
47232 KB |
1_09.txt |
AC |
1191 ms |
47232 KB |
1_10.txt |
AC |
1190 ms |
47232 KB |
1_11.txt |
AC |
1207 ms |
47232 KB |
1_12.txt |
AC |
1003 ms |
47232 KB |
1_13.txt |
AC |
1157 ms |
47232 KB |
1_14.txt |
AC |
979 ms |
47232 KB |
1_15.txt |
AC |
1028 ms |
47232 KB |
1_16.txt |
AC |
1067 ms |
47232 KB |
1_17.txt |
AC |
1164 ms |
47232 KB |
1_18.txt |
AC |
984 ms |
47232 KB |
1_19.txt |
AC |
1201 ms |
47232 KB |