Submission #225777

#	Time	Username	Problem	Language	Result	Execution time	Memory
225777		aloo123	Asceticism (JOI18_asceticism)	C++14	49 / 100	166 ms	94456 KiB

asceticism

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
using namespace std;
 
const ll N =(2e5+5);
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238 
  
double circumference(double r) 
{ 
    double cir = 2.0;
    cir*=PI;
    cir*=r; 
    return cir; 
} 
ll m;
long long binpow(long long a, long long b) {
    a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD;
        a = (a * a)%MOD;
 
        
        b >>= 1;
    }
    res%=MOD;
    return res;
}
ll t[3005][3005];
void solve(){
    
    ll n,k;
    cin>>n>>k;

    t[1][1] = 1;
    // for(int i =0;i<=n;i++){
    //     for(int j =0;j<=n;j++){
    //         t[i][j] = 1;
    //     }
    // }
    for(ll i =1;i<=n;i++){
        for(ll j = 1;j<=i;j++){
            if(i==1&&j==1)continue;
            ll xd = t[i-1][j]%MOD;
            xd = (xd * j)%MOD;
            if(xd < 0) xd += MOD;
            t[i][j] = (t[i][j] + xd)%MOD;
            if(t[i][j]<0)t[i][j]+=MOD;
            //(i-j+1) * t[i-1][j-1]
            xd = (i-j+1);
            xd  = (xd * t[i-1][j-1])%MOD;
            t[i][j] = (t[i][j] + xd)%MOD;
            if(t[i][j]<0)t[i][j]+=MOD;
        }
    }
    // for(int i =1;i<=n;i++){
    //     for(int j =1;j<=n;j++){
    //         cout<<t[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<t[n][k]<<endl;



}
 
 
int main(){
    ios_base::sync_with_stdio(0);
     cin.tie(NULL);
     
    ll t=1;
    while(t--){
        solve();
    }
     
 
 
    return 0;     
    
        
}//42364286 418930126
// (3,2)
// (0,0) -> (-1,0) -> (-1,2) -> (3,2)

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51