Submission #43997

#	Time	Username	Problem	Language	Result	Execution time	Memory
43997		zscoder	Asceticism (JOI18_asceticism)	C++17	100 / 100	68 ms	2372 KiB

asceticism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const int MOD = 1e9 + 7;

int add(int a, int b)
{
	a+=b; while(a>=MOD) a-=MOD;
	return a;
}

int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a); b>>=1;
	}
	return r;
}

int ifact[111111];
int fact[111111];
int pow2[111111];
int ipow2[111111];
int choose(int n, int r)
{
	if(r<0) return 0;
	if(n<r) return 0;
	if(r==0) return 1;
	return mult(fact[n],mult(ifact[r],ifact[n-r]));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	fact[0]=ifact[0]=1; pow2[0]=ipow2[0]=1;
	for(int i=1;i<=100111;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		ipow2[i] = modpow(pow2[i], MOD-2);
	}
	for(int i=1;i<=100111;i++) 
	{
		fact[i]=mult(fact[i-1],i); ifact[i] = modpow(fact[i],MOD-2);
	}
	int ans=0;
	m--;
	for(int i=0;i<=m+1;i++)
	{
		ans = add(ans, mult(modpow(MOD-1,i),mult(choose(n+1,i),modpow(m-i+1,n))));
	}
	cout<<ans<<'\n';
}

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