oj.uz

Submission #15221

# Submission time Handle Problem Language Result Execution time Memory
15221 2015-07-12T04:06:42 Z xhae 접미사 배열의 개수 (kriii3_W) C++14
0 / 46
 32 ms 24520 KB 
#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++) {
    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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24520 KB Output is correct
2 Incorrect 32 ms 24520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -