제출 #312788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312788		YJU	Asceticism (JOI18_asceticism)	C++14	100 / 100	80 ms	6680 KiB

asceticism

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,fac[N],rfac[N];

ll C(ll a,ll b){
	return fac[a]*rfac[b]%MOD*rfac[a-b]%MOD;
}

ll po(ll base,ll ti){
	ll res=1;
	for(;ti;ti>>=1,base=base*base%MOD){
		if(ti&1)res=res*base%MOD;
	}
	return res;
}

ll cal(ll k){
	ll tmp=0;
	for(int i=0,o=1;i<k;i++,o=-o)tmp=(tmp+1LL*o*C(n,i)*po(k-i,n))%MOD;
	return (tmp+MOD)%MOD;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	fac[0]=rfac[0]=1;
	REP1(i,N-1)fac[i]=i*fac[i-1]%MOD,rfac[i]=rfac[i-1]*po(i,MOD-2)%MOD;
	ll ans=cal(m)-cal(m-1);
	cout<<(ans%MOD+MOD)%MOD<<"\n";
	return 0;
}

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