16 dumb

16.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int mexp(int v, int e, int MOD) {
  int ret = 1;
  if (e == 0) return ret;
  for(int i = 31 - __builtin_clz(e); i >= 0; i--) {
    ret = (ret * ret) % MOD;
    if(e & 1 << i) {
      ret = (ret * v) % MOD;
    }
  }
  return ret;
}


const int MOD = 10;
const int TOTIENT = 4;
const int P[] = {2, 5};
const int PRIMES = 2;

struct mint {
  mint(int x) {
    for (size_t i = 0; i < PRIMES; i++) {
      for (f[i] = 0; x % P[i] == 0; f[i]++) {
        x /= P[i];
      }
    }
    r = x % MOD;
  }

  mint& operator *=(const mint& x) {
    for (size_t i = 0; i < PRIMES; i++) {
      f[i] += x.f[i];
    }
    r = (r * x.r) % MOD;
    return *this;
  }

  mint& operator /=(const mint& x) {
    for (size_t i = 0; i < PRIMES; i++) {
      f[i] -= x.f[i];
    }
    r = (r * mexp(x.r, TOTIENT - 1, MOD)) % MOD;
    return *this;
  }
  
  int eval() {
    int res = r;
    for (size_t i = 0; i < PRIMES; i++) {
      res = (res * mexp(P[i], f[i], MOD)) % MOD;
    }
    return res;
  }

  int f[PRIMES];
  int r;
};

const size_t PHASES = 100;
const size_t MULTIPLICITY = 10000;

int main() {
  string S; cin >> S;
  size_t N = S.size();
  size_t offset = atoi(S.substr(0, 7).c_str());

  for (size_t i = offset; i < offset + 8; i++) {
    int res = 0;

    mint r = 1;
    for (size_t j = i; j < N * MULTIPLICITY; j++) {
      res += (S[j % N] - '0') * r.eval();
      r *= PHASES + j - i;
      r /= j - i + 1;
    }
    cout << res % 10;
  }
  cout << endl;

  return 0;
}
                                                                                       85,1          Bo