Submission #225775

#	Time	Username	Problem	Language	Result	Execution time	Memory
225775		aloo123	Asceticism (JOI18_asceticism)	C++14	49 / 100	157 ms	94364 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;
    t[1][0] = 1;
    //t[0][0] = 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 = 0;j<i;j++){
      //      if(i==1&&j==1)continue;
            ll xd = t[i][j]%MOD;
            xd = (xd*(j+1))%MOD;
            if(xd<0)xd+=MOD;
            t[i+1][j] = (t[i+1][j]+xd)%MOD;
            if(t[i+1][j]<0)t[i+1][j]+=MOD;
            ll x = t[i][j];
            x = (x*(i-j))%MOD;
            if(x<0)x+=MOD;
            t[i+1][j+1] = (t[i+1][j+1]+x)%MOD;
            
            if(t[i+1][j+1]<0)t[i][j]+=MOD;
            //if(t[i][j] ==0)t[i][j]++;
        }
    }
    // for(int i =1;i<=n;i++){
    //     for(int j =1;j<=n;j++){
    //         cout<<t[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<t[n][k-1]<<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