Submission #1015770
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define pb emplace_back
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
// head
struct Mod{
unsigned n;
Mod() : n(0){}
Mod( ll x ){
if( x < 0 ) n = x%MOD+MOD;
else n = x%MOD;
}
};
Mod operator + ( Mod a , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
Mod res = 1;
while( k ){
if( k & 1 ) res *= x;
k /= 2;
x *= x;
}
return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
ll d = a;
if( b != 0 ){
d = extgcd( b , a % b , y , x );
y -= a / b * x;
} else {
x = 1, y = 0;
}
return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
Mod operator / ( Mod a , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }
struct Factorial{
vector<Mod> v;
Factorial( int max_n ){
v = vector<Mod>( max_n , 1 );
FOR( i , 1 , max_n ) v[i] = v[i-1] * i;
}
int size(){
return v.size();
}
Mod operator [] ( int id ){
return v[id];
}
};
struct Factorial_inv{
vector<Mod> v;
Factorial_inv( Factorial &f ){
v = vector<Mod>( f.size() );
REP( i , f.size() ) v[i] = inv( f[i] );
}
Mod operator [] ( int id ){
return v[id];
}
};
struct Combination{
Factorial *f;
Factorial_inv *finv;
Combination( Factorial &arg_f , Factorial_inv &arg_finv ){
f = &arg_f;
finv = &arg_finv;
}
Mod operator () ( int a , int b ){
return (*f)[a] * (*finv)[b] * (*finv)[a-b];
}
};
Factorial fact( 4000010 );
Factorial_inv finv( fact );
Combination comb( fact , finv );
int n, k;
Mod dp[2010][2010];
int main(){
n = in();
k = in();
if( k == 1 ){
cout << 1 << endl;
return 0;
}
dp[0][0] = 1;
REP( i , n+1 ){
if( i == 0 ){
dp[i][i] = 1;
} else {
dp[i][i] = dp[i-1][i];
}
FOR( j , i+1 , n+1 ){
if( i > 0 ){
dp[i][j] = dp[i-1][j];
}
dp[i][j] += dp[i][j-1] * comb( i + j * ( k - 1 ) - 1 , k - 2 );
}
}
/*
REP( i , n+1 ){
REP( j , n+1 ){
cout << dp[i][j].n << " ";
}
cout << endl;
}
*/
cout << ( dp[n][n] * fact[n] ).n << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Leftmost Ball |
User |
joisino |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
3936 Byte |
Status |
AC |
Exec Time |
1341 ms |
Memory |
47360 KB |
Compile Error
./Main.cpp: In function ‘ll in()’:
./Main.cpp:44:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
^
./Main.cpp: In function ‘std::string stin()’:
./Main.cpp:45:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
^
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 |
1290 ms |
47360 KB |
0_01.txt |
AC |
1289 ms |
47360 KB |
0_02.txt |
AC |
1287 ms |
47232 KB |
0_03.txt |
AC |
1338 ms |
47232 KB |
1_00.txt |
AC |
1287 ms |
47232 KB |
1_01.txt |
AC |
1288 ms |
47232 KB |
1_02.txt |
AC |
1288 ms |
47232 KB |
1_03.txt |
AC |
1339 ms |
47232 KB |
1_04.txt |
AC |
1335 ms |
47232 KB |
1_05.txt |
AC |
1341 ms |
47232 KB |
1_06.txt |
AC |
1337 ms |
47360 KB |
1_07.txt |
AC |
1332 ms |
47232 KB |
1_08.txt |
AC |
1334 ms |
47232 KB |
1_09.txt |
AC |
1336 ms |
47232 KB |
1_10.txt |
AC |
1336 ms |
47232 KB |
1_11.txt |
AC |
1334 ms |
47232 KB |
1_12.txt |
AC |
1294 ms |
47232 KB |
1_13.txt |
AC |
1327 ms |
47232 KB |
1_14.txt |
AC |
1290 ms |
47232 KB |
1_15.txt |
AC |
1298 ms |
47232 KB |
1_16.txt |
AC |
1303 ms |
47232 KB |
1_17.txt |
AC |
1328 ms |
47232 KB |
1_18.txt |
AC |
1289 ms |
47232 KB |
1_19.txt |
AC |
1335 ms |
47232 KB |