Submission #15225

#	Time	Username	Problem	Language	Result	Execution time	Memory
15225		xhae	접미사 배열의 개수 (kriii3_W)	C++14	46 / 46	179 ms	24520 KiB

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 / 10
• Subtask 2: 36 / 36