Submission #14660707


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)

using namespace std;
typedef long long int ll;

// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
 public:
  int64_t a;

  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
};
// }}}

const ll M = 1e9 + 7;
using mint = modint<M>;
std::vector<ll> fac(3000000, 1), finv(3000000, 1), inv(3000000, 1);

void c4_init(ll m) {
    for (ll i = 2; i < 3000000; i++) {
        fac[i] = fac[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        finv[i] = finv[i - 1] * inv[i] % m;
    }
}

ll c4(ll n, ll k, ll m) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % m) % m;
}

ll N, K;
mint ans(0);
string s;

int main(void) {
  c4_init(M);
  cin >> K >> s;
  N = s.size();
  for (ll j = N-1; j < N + K; j++) {
    ans += mint(c4(j, N-1, M)) * mint(25).pow(j- (N-1)) * mint(26).pow((N+K-1) - j);
  }
  cout << ans.value() << endl;
  return 0;
}

Submission Info

Submission Time
Task F - Strivore
User bobuhiro11
Language C++ (GCC 9.2.1)
Score 600
Code Size 2459 Byte
Status
Exec Time 805 ms
Memory 75548 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt
Case Name Status Exec Time Memory
sample_01.txt 364 ms 73004 KB
sample_02.txt 361 ms 73048 KB
sub1_01.txt 805 ms 75540 KB
sub1_02.txt 793 ms 75544 KB
sub1_03.txt 772 ms 75548 KB
sub1_04.txt 769 ms 75388 KB
sub1_05.txt 375 ms 73892 KB
sub1_06.txt 373 ms 74404 KB
sub1_07.txt 379 ms 74396 KB
sub1_08.txt 360 ms 75544 KB
sub1_09.txt 377 ms 75540 KB
sub1_10.txt 359 ms 75536 KB
sub1_11.txt 616 ms 73216 KB
sub1_12.txt 503 ms 73264 KB
sub1_13.txt 772 ms 73008 KB
sub1_14.txt 415 ms 73796 KB
sub1_15.txt 360 ms 73704 KB
sub1_16.txt 371 ms 73556 KB
sub1_17.txt 367 ms 73252 KB
sub1_18.txt 364 ms 73004 KB
sub1_19.txt 368 ms 73204 KB
sub1_20.txt 624 ms 74508 KB
sub1_21.txt 550 ms 74008 KB
sub1_22.txt 643 ms 74468 KB
sub1_23.txt 498 ms 74084 KB
sub1_24.txt 759 ms 74128 KB
sub1_25.txt 645 ms 74128 KB
sub1_26.txt 437 ms 74120 KB
sub1_27.txt 538 ms 74392 KB
sub1_28.txt 504 ms 73612 KB