oj.uz

Submission #58891

# Submission time Handle Problem Language Result Execution time Memory
58891 2018-07-19T18:45:35 Z TadijaSebez Asceticism (JOI18_asceticism) C++11
0 / 100
 7 ms 2008 KB 
#include <stdio.h>
#define ll long long
const int N=200050;
const int mod=1000000007;
int F[N],I[N];
int pow(int x, int k){ int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
int get(int n, int k){ return (ll)F[n]*I[k]%mod*I[n-k]%mod;}
int calc(int n, int k)
{
	if(k>n) return 0;
	int ret=0;
	for(int i=k;i;i--)
	{
		int add=(ll)get(k,i)*pow(i,n)%mod;
		if((k-i)&1) ret=(ret-add+mod)%mod;
		else ret=(ret+add)%mod;
	}
	return (ll)ret*I[k]%mod;
}
int main()
{
	int n,k,x,i,sum=0;
	F[0]=1;for(i=1;i<N;i++) F[i]=(ll)F[i-1]*i%mod;
	I[N-1]=pow(F[N-1],mod-2);for(i=N-2;i>=0;i--) I[i]=(ll)I[i+1]*(i+1)%mod;
	scanf("%i %i",&n,&k);
	printf("%i\n",calc(n,k));
	return 0;
}

Compilation message

asceticism.cpp: In function 'int main()':
asceticism.cpp:22:10: warning: unused variable 'x' [-Wunused-variable]
  int n,k,x,i,sum=0;
          ^
asceticism.cpp:22:14: warning: unused variable 'sum' [-Wunused-variable]
  int n,k,x,i,sum=0;
              ^~~
asceticism.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 6 ms 1896 KB Output is correct
3 Incorrect 7 ms 2008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 6 ms 1896 KB Output is correct
3 Incorrect 7 ms 2008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 6 ms 1896 KB Output is correct
3 Incorrect 7 ms 2008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 6 ms 1896 KB Output is correct
3 Incorrect 7 ms 2008 KB Output isn't correct
4 Halted 0 ms 0 KB -