Submission #225787

#	Time	Username	Problem	Language	Result	Execution time	Memory
225787		aloo123	Asceticism (JOI18_asceticism)	C++14	100 / 100	129 ms	2732 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);
#define int ll
using namespace std;
 
const ll N =(2e5+5);
 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;
}
int fac[N]; 
int power(int x, int y, int p) 
{ 
    int res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or 
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
int modInverse(int n, int p) 
{ 
    return power(n, p-2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
void comp(){

    fac[0] = 1; 
    for (int i=1 ; i<N; i++) 
        fac[i] = fac[i-1]*i%MOD; 
}

int nCrModPFermat(int n, int r, int p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 

void solve(){
    comp();
    ll n,k;
    cin>>n>>k;
    ll ans = 0;
    ll gg[k+1];
    for(ll j = 0;j<=k;j++){
        gg[j] = nCrModPFermat(n+1,j,MOD);
    }
    for(ll j = 0;j<=k;j++){
      //  cout<<gg[j]<<endl;
        ll xd=1;
        
        xd = (xd * binpow(k-j,n))%MOD;
        if(xd<0)xd+=MOD;
        xd = (xd * gg[j])%MOD;
        if(xd<0)xd+=MOD;
        if(j&1)
        ans = (ans - xd)%MOD;
        else
            ans=(ans + xd)%MOD;
        if(ans<0)ans+=MOD;
    }
    cout<<ans<<endl;
       
   


}
 
 
signed main(){
    ios_base::sync_with_stdio(0);
     cin.tie(NULL);
     
    ll t=1;
    while(t--){
        solve();
    }
     
 
 
    
        
}//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: 51 / 51