Submission #347925

#	Time	Username	Problem	Language	Result	Execution time	Memory
347925		CaroLinda	Asceticism (JOI18_asceticism)	C++14	100 / 100	18 ms	1132 KiB

asceticism

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )

const int MAX = 1e5+10 ;
const ll MOD = 1e9+7 ;

using namespace std ;

int N , K ;
ll inv[MAX] ;

ll expo(ll num, ll e )
{
	if(e == 0 ) return 1LL ;

	ll aux = expo(num, e>>1 ) ;
	aux = (aux * aux ) % MOD ;

	if(e&1) aux = (aux * num ) % MOD ;

	return aux ;

}

int main()
{
	scanf("%d %d", &N, &K ) ;

	inv[1] = 1 ;
	for(int i = 2 ; i <= N+1 ; i++ ) 
	{
		inv[i] = ( ( MOD/i ) * inv[ MOD%i ] ) % MOD ;
		inv[i] = MOD - inv[i] ;
	}
	
	ll ans =0 ;
	ll bin ;

	K = N - K ;
	for(int j = 0 ; j <= K+1 ; j++ )
	{
		if( j == 0 ) bin = 1LL ;
		else
		{
			bin = ( bin * (N+1-(j-1) ) ) % MOD ;
			bin = ( bin * inv[j] ) % MOD ;			  	
		}				

		if( j&1 ) ans -= (bin * expo(K-j+1, N ) ) % MOD ;
		else ans += (bin * expo(K-j+1, N) ) % MOD ;

		if( ans >= MOD ) ans -= MOD ;
		if( ans < 0 ) ans  += MOD ;

	}

	printf("%lld\n", ans ) ;

}

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d %d", &N, &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~

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