Submission #930946

#	Time	Username	Problem	Language	Result	Execution time	Memory
930946		manizare	Asceticism (JOI18_asceticism)	C++14	100 / 100	14 ms	3676 KiB

asceticism

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
const int maxn = 2e5 + 10 , mod = 1e9 + 7 , b = 56 , maxp = 15e5 + 10, inf=  1e9+10  , lg = 20;
int f[maxn] , inv[maxn] ;

int po(int a, int b){
    if(b==0)return 1;
    int v = po(a,b/2) ;
    v= v*v %mod ;
    if(b&1) v= v*a % mod ;
    return v ;
}
int c(int n , int k){
    if(k < 0 || n < k)return 0 ;
    return f[n]*inv[k]%mod*inv[n-k]%mod; 
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    f[0] =1 ;
    rep(i , 1 , maxn-1)f[i] =f[i-1] * i % mod ;
    inv[maxn-1] = po(f[maxn-1] , mod-2) ;
    per(i , maxn-2 , 0){
        inv[i] = inv[i+1] * (i+1) % mod ;
    }
    int n , k ;
    cin >> n >> k ;
    int ans =0 ;
    per(i , k , 1){
        int x = po(i , n) * c(n+1 , k-i) %mod;
        if((i-k)%2==0){
            ans = (ans + x)%mod ;
        }else{
            ans = (ans - x + mod)%mod ;
        }
    }
    cout << ans << '\n' ;
}
/*

*/

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