Submission #15225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15225	2015-07-12T04:10:17 Z	xhae	접미사 배열의 개수 (kriii3_W)	C++14	46 / 46	179 ms	24520 KB

W

#include <cstdio>
#include <algorithm>

using namespace std;

const int mod = 1000000007;
long long invs[1000003];
long long fact[1000003];
long long ifact[1000003];

long long powmod(long long b, long long n) {
  long long ret = 1;
  while(n) {
    if (n & 1) {
      ret *= b;
      ret %= mod;
    }
    b *= b;
    b %= mod;
    n >>= 1;
  }
  return ret;
}

int main(){
  int n, sigma;
  scanf("%d%d",&n,&sigma);
  long long ans = 0;
  invs[1] = 1;
  for (int i = 2; i <= 1000002; i++) invs[i] = invs[mod%i] * (mod - mod / i) % mod;
  fact[0] = 1;
  for (int i = 1; i <= 1000002; i++) fact[i] = fact[i-1] * i % mod;
  ifact[0] = 1;
  for (int i = 1; i <= 1000002; i++) ifact[i] = ifact[i-1] * invs[i] % mod;

  for (int i = 0; i < sigma && i <= n; i++) {
    long long cursum = fact[n] * ifact[n-i] % mod * ifact[i] % mod * powmod(sigma - i, n) % mod;
    if (i % 2) {
      ans -= cursum;
    } else {
      ans += cursum;
    }

    ans %= mod;
  }
  ans += mod;
  ans %= mod;
  printf("%lld\n", ans);
  return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	24520 KB	Output is correct
2	Correct	35 ms	24520 KB	Output is correct
3	Correct	35 ms	24520 KB	Output is correct
4	Correct	28 ms	24520 KB	Output is correct
5	Correct	28 ms	24520 KB	Output is correct
6	Correct	35 ms	24520 KB	Output is correct
7	Correct	35 ms	24520 KB	Output is correct
8	Correct	31 ms	24520 KB	Output is correct
9	Correct	36 ms	24520 KB	Output is correct
10	Correct	35 ms	24520 KB	Output is correct
11	Correct	36 ms	24520 KB	Output is correct
12	Correct	36 ms	24520 KB	Output is correct

Subtask #2

36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24520 KB	Output is correct
2	Correct	35 ms	24520 KB	Output is correct
3	Correct	23 ms	24520 KB	Output is correct
4	Correct	32 ms	24520 KB	Output is correct
5	Correct	34 ms	24520 KB	Output is correct
6	Correct	46 ms	24520 KB	Output is correct
7	Correct	48 ms	24520 KB	Output is correct
8	Correct	75 ms	24520 KB	Output is correct
9	Correct	78 ms	24520 KB	Output is correct
10	Correct	122 ms	24520 KB	Output is correct
11	Correct	179 ms	24520 KB	Output is correct
12	Correct	119 ms	24520 KB	Output is correct