Submission #914858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914858	2024-01-22T18:59:06 Z	amirhoseinfar1385	Asceticism (JOI18_asceticism)	C++17	4 / 100	3 ms	2000 KB

asceticism

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long mod=1e9+7;
long long fact[maxn],revfact[maxn];

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

void aval(){
	fact[0]=1;
	for(long long i=1;i<maxn;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(long long i=maxn-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	return 1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
}

int main(){
	aval();
	long long n,k;
	cin>>n>>k;
	long long res=0;
	for(long long i=k;i>=1;i--){
		long long fake=mypow(i,n)*c(n+1,k-i)%mod;
		if(i&1){
			res-=fake;
		}
		else{
			res+=fake;
		}
		//cout<<i<<" "<<fake<<" "<<mypow(i,n)<<" "<<c(n+1,k-i)<<endl;
	}
	//cout<<res<<endl;
	//res+=1000000*mod;
	//res%=mod;
	res=abs(res);
	res%=mod;
	cout<<res<<"\n";
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1884 KB	Output is correct
2	Correct	3 ms	1884 KB	Output is correct
3	Correct	3 ms	1964 KB	Output is correct
4	Correct	3 ms	1884 KB	Output is correct
5	Correct	3 ms	1884 KB	Output is correct
6	Correct	3 ms	1884 KB	Output is correct
7	Correct	3 ms	1792 KB	Output is correct
8	Correct	3 ms	1884 KB	Output is correct
9	Correct	3 ms	2000 KB	Output is correct
10	Correct	3 ms	1884 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1884 KB	Output is correct
2	Correct	3 ms	1884 KB	Output is correct
3	Correct	3 ms	1964 KB	Output is correct
4	Correct	3 ms	1884 KB	Output is correct
5	Correct	3 ms	1884 KB	Output is correct
6	Correct	3 ms	1884 KB	Output is correct
7	Correct	3 ms	1792 KB	Output is correct
8	Correct	3 ms	1884 KB	Output is correct
9	Correct	3 ms	2000 KB	Output is correct
10	Correct	3 ms	1884 KB	Output is correct
11	Correct	3 ms	1880 KB	Output is correct
12	Correct	3 ms	1904 KB	Output is correct
13	Correct	3 ms	1884 KB	Output is correct
14	Correct	3 ms	1884 KB	Output is correct
15	Incorrect	3 ms	1884 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1884 KB	Output is correct
2	Correct	3 ms	1884 KB	Output is correct
3	Correct	3 ms	1964 KB	Output is correct
4	Correct	3 ms	1884 KB	Output is correct
5	Correct	3 ms	1884 KB	Output is correct
6	Correct	3 ms	1884 KB	Output is correct
7	Correct	3 ms	1792 KB	Output is correct
8	Correct	3 ms	1884 KB	Output is correct
9	Correct	3 ms	2000 KB	Output is correct
10	Correct	3 ms	1884 KB	Output is correct
11	Correct	3 ms	1880 KB	Output is correct
12	Correct	3 ms	1904 KB	Output is correct
13	Correct	3 ms	1884 KB	Output is correct
14	Correct	3 ms	1884 KB	Output is correct
15	Incorrect	3 ms	1884 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1884 KB	Output is correct
2	Correct	3 ms	1884 KB	Output is correct
3	Correct	3 ms	1964 KB	Output is correct
4	Correct	3 ms	1884 KB	Output is correct
5	Correct	3 ms	1884 KB	Output is correct
6	Correct	3 ms	1884 KB	Output is correct
7	Correct	3 ms	1792 KB	Output is correct
8	Correct	3 ms	1884 KB	Output is correct
9	Correct	3 ms	2000 KB	Output is correct
10	Correct	3 ms	1884 KB	Output is correct
11	Correct	3 ms	1880 KB	Output is correct
12	Correct	3 ms	1904 KB	Output is correct
13	Correct	3 ms	1884 KB	Output is correct
14	Correct	3 ms	1884 KB	Output is correct
15	Incorrect	3 ms	1884 KB	Output isn't correct
16	Halted	0 ms	0 KB	-