結果
| 問題 | No.1595 The Final Digit |
| ユーザー |
 Fukucchi
|
| 提出日時 | 2021-07-10 00:10:41 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 26 ms / 2,000 ms |
| コード長 | 26,325 bytes |
| コンパイル時間 | 4,357 ms |
| コンパイル使用メモリ | 202,504 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-01 19:00:34 |
| 合計ジャッジ時間 | 5,365 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 9 ms
5,248 KB |
| testcase_01 | AC | 23 ms
5,376 KB |
| testcase_02 | AC | 3 ms
5,376 KB |
| testcase_03 | AC | 10 ms
5,376 KB |
| testcase_04 | AC | 4 ms
5,376 KB |
| testcase_05 | AC | 3 ms
5,376 KB |
| testcase_06 | AC | 10 ms
5,376 KB |
| testcase_07 | AC | 4 ms
5,376 KB |
| testcase_08 | AC | 9 ms
5,376 KB |
| testcase_09 | AC | 23 ms
5,376 KB |
| testcase_10 | AC | 16 ms
5,376 KB |
| testcase_11 | AC | 23 ms
5,376 KB |
| testcase_12 | AC | 25 ms
5,376 KB |
| testcase_13 | AC | 16 ms
5,376 KB |
| testcase_14 | AC | 26 ms
5,376 KB |
| testcase_15 | AC | 26 ms
5,376 KB |
| testcase_16 | AC | 18 ms
5,376 KB |
| testcase_17 | AC | 9 ms
5,376 KB |
| testcase_18 | AC | 16 ms
5,376 KB |
| testcase_19 | AC | 11 ms
5,376 KB |
コンパイルメッセージ
main.cpp: In member function 'FormalPowerSeries<T, mode>::F& FormalPowerSeries<T, mode>::operator*=(S)':
main.cpp:480:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
480 | auto [d, c] = g.front();
| ^
main.cpp:487:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
487 | for (auto &[j, b] : g) {
| ^
main.cpp: In member function 'FormalPowerSeries<T, mode>::F& FormalPowerSeries<T, mode>::operator/=(S)':
main.cpp:498:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
498 | auto [d, c] = g.front();
| ^
main.cpp:503:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
503 | for (auto &[j, b] : g) {
| ^
ソースコード
/* #region header */
#pragma GCC optimize("O3") //コンパイラ最適化用
#ifdef LOCAL
#define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示
#endif
#define _USE_MATH_DEFINES
#include <algorithm> //sort,二分探索,など
#include <atcoder/all> // CodeForcesの場合ファイルごとに入れる
#include <bitset> //固定長bit集合
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
#include <cassert> //assert(p)で，not pのときにエラー
#include <cctype>
#include <chrono> //実行時間計測
#include <climits>
#include <cmath> //pow,logなど
#include <complex> //複素数
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional> //sortのgreater
#include <iomanip> //setprecision(浮動小数点の出力の誤差)
#include <ios> // std::left, std::right
#include <iostream> //入出力
#include <iterator> //集合演算(積集合,和集合,差集合など)
#include <map>
#include <numeric> //iota(整数列の生成),gcdとlcm,accumulate
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility> //pair
#include <vector>
using namespace std;
using namespace atcoder;
typedef long long LL;
typedef long double LD;
#define ALL(x) x.begin(), x.end()
const long long INF = numeric_limits<long long>::max() / 4;
const int MOD = 1e9 + 7;
// const int MOD=998244353;
//略記
#define FF first
#define SS second
#define int long long
#define stoi stoll
#define LD long double
#define PII pair<int, int>
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(x) (int)((x).size())
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPD(i, n) for (int i = (int)(n) - (int)1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)(b); i++)
#define FORD(i, a, b) for (int i = (int)(b) - (int)1; i >= (int)a; i--)
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1},
Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int in() {
int x;
cin >> x;
return x;
}
// https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed#c%E3%81%A7%E3%81%AE%E5%AE%9F%E8%A3%85
void print() { cout << "\n"; }
template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
cout << head;
if (sizeof...(tail) != 0)
cout << " ";
print(forward<Tail>(tail)...);
}
template <class T> void print(vector<T> &vec) {
for (auto &a : vec) {
cout << a;
if (&a != &vec.back())
cout << " ";
}
cout << "\n";
}
template <class T> void print(set<T> &set) {
for (auto &a : set) {
cout << a << " ";
}
cout << "\n";
}
template <class T> void print(vector<vector<T>> &df) {
for (auto &vec : df) {
print(vec);
}
}
// debug macro
// https://atcoder.jp/contests/abc202/submissions/22815715
namespace debugger {
template <class T> void view(const std::vector<T> &a) {
std::cerr << "{ ";
for (const auto &v : a) {
std::cerr << v << ", ";
}
std::cerr << "\b\b }";
}
template <class T> void view(const std::vector<std::vector<T>> &a) {
std::cerr << "{\n";
for (const auto &v : a) {
std::cerr << "\t";
view(v);
std::cerr << "\n";
}
std::cerr << "}";
}
template <class T, class U> void view(const std::vector<std::pair<T, U>> &a) {
std::cerr << "{\n";
for (const auto &p : a)
std::cerr << "\t(" << p.first << ", " << p.second << ")\n";
std::cerr << "}";
}
template <class T, class U> void view(const std::map<T, U> &m) {
std::cerr << "{\n";
for (const auto &p : m)
std::cerr << "\t[" << p.first << "] : " << p.second << "\n";
std::cerr << "}";
}
template <class T, class U> void view(const std::pair<T, U> &p) {
std::cerr << "(" << p.first << ", " << p.second << ")";
}
template <class T> void view(const std::set<T> &s) {
std::cerr << "{ ";
for (auto &v : s) {
view(v);
std::cerr << ", ";
}
std::cerr << "\b\b }";
}
template <class T> void view(const T &e) { std::cerr << e; }
} // namespace debugger
#ifdef LOCAL
void debug_out() {}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
debugger::view(H);
std::cerr << ", ";
debug_out(T...);
}
#define debug(...) \
do { \
std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \
debug_out(__VA_ARGS__); \
std::cerr << "\b\b]\n"; \
} while (false)
#else
#define debug(...) (void(0))
#endif
long long power(long long x, long long n) {
// O(logn)
// https://algo-logic.info/calc-pow/#toc_id_1_2
long long ret = 1;
while (n > 0) {
if (n & 1)
ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける
x *= x;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
// @brief nCr. O(r log n)。あるいは前処理 O(n), 本処理 O(1)で求められる modint
// の bc を検討。
int comb(int n, int r) {
// https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/
if (n < r)
return 0;
// p holds the value of n*(n-1)*(n-2)...,
// k holds the value of r*(r-1)...
long long p = 1, k = 1;
// C(n, r) == C(n, n-r),
// choosing the smaller value
if (n - r < r)
r = n - r;
if (r != 0) {
while (r) {
p *= n;
k *= r;
// gcd of p, k
long long m = __gcd(p, k);
// dividing by gcd, to simplify
// product division by their gcd
// saves from the overflow
p /= m;
k /= m;
n--;
r--;
}
// k should be simplified to 1
// as C(n, r) is a natural number
// (denominator should be 1 ) .
}
else
p = 1;
// if our approach is correct p = ans and k =1
return p;
}
// MOD
void add(long long &a, long long b) {
a += b;
if (a >= MOD)
a -= MOD;
}
template <class T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
// 負数も含む丸め
long long ceildiv(long long a, long long b) {
if (b < 0)
a = -a, b = -b;
if (a >= 0)
return (a + b - 1) / b;
else
return a / b;
}
long long floordiv(long long a, long long b) {
if (b < 0)
a = -a, b = -b;
if (a >= 0)
return a / b;
else
return (a - b + 1) / b;
}
long long floorsqrt(long long x) {
assert(x >= 0);
long long ok = 0;
long long ng = 1;
while (ng * ng <= x)
ng <<= 1;
while (ng - ok > 1) {
long long mid = (ng + ok) >> 1;
if (mid * mid <= x)
ok = mid;
else
ng = mid;
}
return ok;
}
// @brief a^n mod mod
long long modpower(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1)
res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// @brief s が c を含むか
template <class T> bool contain(const std::string &s, const T &c) {
return s.find(c) != std::string::npos;
}
__attribute__((constructor)) void faster_io() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cerr.tie(nullptr);
}
/* #endregion */
/* #region Math Formal Power Series */
// 二項係数ライブラリ
template <class T> struct BiCoef {
vector<T> fact_, inv_, finv_;
constexpr BiCoef() {}
constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
init(n);
}
// @brief O(n)
constexpr void init(int n, int mod) noexcept {
fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
int MOD = mod;
for (int i = 2; i < n; i++) {
fact_[i] = fact_[i - 1] * i;
inv_[i] = -inv_[MOD % i] * (MOD / i);
finv_[i] = finv_[i - 1] * inv_[i];
}
}
// @brief O(1)
constexpr T com(int n, int k) const noexcept {
if (n < k || n < 0 || k < 0)
return 0;
return fact_[n] * finv_[k] * finv_[n - k];
}
// @brief O(1)
constexpr T fact(int n) const noexcept {
if (n < 0)
return 0;
return fact_[n];
}
// @brief O(1)
constexpr T perm(int n, int k) const noexcept {
if (n < k || n < 0 || k < 0)
return 0;
return fact_[n] * finv_[k] * finv_[n - k] * fact_[k];
}
// @brief O(1)
constexpr T inv(int n) const noexcept {
if (n < 0)
return 0;
return inv_[n];
}
// @brief O(1)
constexpr T finv(int n) const noexcept {
if (n < 0)
return 0;
return finv_[n];
}
};
enum Mode {
FAST = 1,
NAIVE = -1,
};
template <class T, Mode mode = FAST> struct FormalPowerSeries : std::vector<T> {
using std::vector<T>::vector;
using std::vector<T>::size;
using std::vector<T>::resize;
using std::vector<T>::begin;
using std::vector<T>::insert;
using std::vector<T>::erase;
using F = FormalPowerSeries;
using S = std::vector<std::pair<int, T>>;
F &operator+=(const F &g) {
for (int i = 0; i < (int)(std::min((*this).size(), g.size())); i++)
(*this)[i] += g[i];
return *this;
}
F &operator+=(const T &t) {
assert((int)((*this).size()));
(*this)[0] += t;
return *this;
}
F &operator-=(const F &g) {
for (int i = 0; i < (int)(std::min((*this).size(), g.size())); i++)
(*this)[i] -= g[i];
return *this;
}
F &operator-=(const T &t) {
assert(SZ((*this)));
(*this)[0] -= t;
return *this;
}
F &operator*=(const T &t) {
for (int i = 0; i < SZ((*this)); ++i)
(*this)[i] *= t;
return *this;
}
F &operator/=(const T &t) {
T div = t.inv();
for (int i = 0; i < SZ(*this); ++i)
(*this)[i] *= div;
return *this;
}
F &operator>>=(const int sz) {
assert(sz >= 0);
int n = (*this).size();
(*this).erase((*this).begin(), (*this).begin() + std::min(sz, n));
(*this).resize(n);
return *this;
}
F &operator<<=(const int sz) {
assert(sz >= 0);
int n = (*this).size();
(*this).insert((*this).begin(), sz, T(0));
(*this).resize(n);
return *this;
}
F &operator%=(const F &g) { return *this -= *this / g * g; }
F &operator=(const std::vector<T> &v) {
int n = (*this).size();
for (int i = 0; i < n; ++i)
(*this)[i] = v[i];
return *this;
}
F operator-() const {
F ret = *this;
return ret * -1;
}
F &operator*=(const F &g) {
if (mode == FAST) {
int n = (*this).size();
auto tmp = atcoder::convolution(*this, g);
for (int i = 0; i < n; ++i)
(*this)[i] = tmp[i];
return *this;
} else {
int n = (*this).size(), m = g.size();
for (int i = n - 1; i >= 0; --i) {
(*this)[i] *= g[0];
for (int j = 1; j < std::min(i + 1, m); j++)
(*this)[i] += (*this)[i - j] * g[j];
}
return *this;
}
}
F &operator/=(const F &g) {
if ((*this).size() < g.size()) {
(*this).assign((*this).size(), T(0));
return *this;
}
if (mode == FAST) {
int old = (*this).size();
int n = (*this).size() - g.size() + 1;
*this = ((*this).rev().pre(n) * g.rev().inv(n));
(*this).rev_inplace();
(*this).resize(old);
return *this;
} else {
assert(g[0] != T(0));
T ig0 = g[0].inv();
int n = (*this).size(), m = g.size();
for (int i = 0; i < n; ++i) {
for (int j = 1; j < std::min(i + 1, m); ++j)
(*this)[i] -= (*this)[i - j] * g[j];
(*this)[i] *= ig0;
}
return *this;
}
}
F &operator*=(S g) {
int n = (*this).size();
auto [d, c] = g.front();
if (!d)
g.erase(g.begin());
else
c = 0;
for (int i = n - 1; i >= 0; --i) {
(*this)[i] *= c;
for (auto &[j, b] : g) {
if (j > i)
break;
(*this)[i] += (*this)[i - j] * b;
}
}
return *this;
}
F &operator/=(S g) {
int n = (*this).size();
auto [d, c] = g.front();
assert(!d and c != 0);
T ic = c.inv();
g.erase(g.begin());
for (int i = 0; i < n; ++i) {
for (auto &[j, b] : g) {
if (j > i)
break;
(*this)[i] -= (*this)[i - j] * b;
}
(*this)[i] *= ic;
}
return *this;
}
F operator+(const F &g) const { return F(*this) += g; }
F operator+(const T &t) const { return F(*this) += t; }
F operator-(const F &g) const { return F(*this) -= g; }
F operator-(const T &t) const { return F(*this) -= t; }
F operator*(const F &g) const { return F(*this) *= g; }
F operator*(const T &t) const { return F(*this) *= t; }
F operator/(const F &g) const { return F(*this) /= g; }
F operator/(const T &t) const { return F(*this) /= t; }
F operator%(const F &g) const { return F(*this) %= g; }
F operator*=(const S &g) const { return F(*this) *= g; }
F operator/=(const S &g) const { return F(*this) /= g; }
F pre(int d) const {
return F((*this).begin(),
(*this).begin() + std::min((int)(*this).size(), d));
}
F &shrink() {
while (!(*this).empty() and (*this).back() == T(0))
(*this).pop_back();
return *this;
}
F &rev_inplace() {
reverse((*this).begin(), (*this).end());
return *this;
}
F rev() const { return F(*this).rev_inplace(); }
// *=(1 + cz^d)
F &multiply(const int d, const T c) {
int n = (*this).size();
if (c == T(1))
for (int i = n - d - 1; i >= 0; --i)
(*this)[i + d] += (*this)[i];
else if (c == T(-1))
for (int i = n - d - 1; i >= 0; --i)
(*this)[i + d] -= (*this)[i];
else
for (int i = n - d - 1; i >= 0; --i)
(*this)[i + d] += (*this)[i] * c;
return *this;
}
// /=(1 + cz^d)
F ÷(const int d, const T c) {
int n = (*this).size();
if (c == T(1))
for (int i = 0; i < n - d; ++i)
(*this)[i + d] -= (*this)[i];
else if (c == T(-1))
for (int i = 0; i < n - d; ++i)
(*this)[i + d] += (*this)[i];
else
for (int i = 0; i < n - d; ++i)
(*this)[i + d] -= (*this)[i] * c;
return *this;
}
// @brief O(N)
T eval(const T &t) const {
int n = (*this).size();
T res = 0, tmp = 1;
for (int i = 0; i < n; ++i)
res += (*this)[i] * tmp, tmp *= t;
return res;
}
// @brief O(n log n). FAST のみ
F inv(int deg = -1) const {
int n = (*this).size();
assert(mode == FAST and n and (*this)[0] != 0);
if (deg == -1)
deg = n;
assert(deg > 0);
F res{(*this)[0].inv()};
while (SZ(res) < deg) {
int m = res.size();
F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);
f.resize(m * 2), atcoder::internal::butterfly(f);
r.resize(m * 2), atcoder::internal::butterfly(r);
for (int i = 0; i < m * 2; ++i)
f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
f.erase(f.begin(), f.begin() + m);
f.resize(m * 2), atcoder::internal::butterfly(f);
for (int i = 0; i < m * 2; ++i)
f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
T iz = T(m * 2).inv();
iz *= -iz;
for (int i = 0; i < m; ++i)
f[i] *= iz;
res.insert(res.end(), f.begin(), f.begin() + m);
}
res.resize(deg);
return res;
}
// @brief Ο(N)
F &diff_inplace() {
int n = (*this).size();
for (int i = 1; i < n; ++i)
(*this)[i - 1] = (*this)[i] * i;
(*this)[n - 1] = 0;
return *this;
}
F diff() const { F(*this).diff_inplace(); }
// @brief Ο(N)
F &integral_inplace() {
int n = (*this).size(), mod = T::mod();
std::vector<T> inv(n);
{
inv[1] = 1;
for (int i = 2; i < n; ++i)
inv[i] = T(mod) - inv[mod % i] * (mod / i);
}
for (int i = n - 2; i >= 0; --i)
(*this)[i + 1] = (*this)[i] * inv[i + 1];
(*this)[0] = 0;
return *this;
}
F integral() const { return F(*this).integral_inplace(); }
// @brief Ο(NlogN). FAST のみ
F &log_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 1);
F f_inv = (*this).inv();
(*this).diff_inplace();
(*this) *= f_inv;
(*this).integral_inplace();
return *this;
}
F log() const { return F(*this).log_inplace(); }
//Ο(NlogN)
F &deriv_inplace() {
int n = (*this).size();
assert(n);
for (int i = 2; i < n; ++i)
(*this)[i] *= i;
(*this).erase((*this).begin());
(*this).push_back(0);
return *this;
}
F deriv() const { return F(*this).deriv_inplace(); }
// @brief Ο(NlogN). FAST のみ
F &exp_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 0);
F g{1};
(*this)[0] = 1;
F h_drv((*this).deriv());
for (int m = 1; m < n; m *= 2) {
F f((*this).begin(), (*this).begin() + m);
f.resize(2 * m), atcoder::internal::butterfly(f);
auto mult_f = [&](F &p) {
p.resize(2 * m);
atcoder::internal::butterfly(p);
for (int i = 0; i < 2 * m; ++i)
p[i] *= f[i];
atcoder::internal::butterfly_inv(p);
p /= 2 * m;
};
if (m > 1) {
F g_(g);
g_.resize(2 * m), atcoder::internal::butterfly(g_);
for (int i = 0; i < 2 * m; ++i)
g_[i] *= g_[i] * f[i];
atcoder::internal::butterfly_inv(g_);
T iz = T(-2 * m).inv();
g_ *= iz;
g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);
}
F t((*this).begin(), (*this).begin() + m);
t.deriv_inplace();
{
F r{h_drv.begin(), h_drv.begin() + m - 1};
mult_f(r);
for (int i = 0; i < m; ++i)
t[i] -= r[i] + r[m + i];
}
t.insert(t.begin(), t.back());
t.pop_back();
t *= g;
F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));
v.resize(m);
t.insert(t.begin(), m - 1, 0);
t.push_back(0);
t.integral_inplace();
for (int i = 0; i < m; ++i)
v[i] -= t[m + i];
mult_f(v);
for (int i = 0; i < std::min(n - m, m); ++i)
(*this)[m + i] = v[i];
}
return *this;
}
F exp() const { return F(*this).exp_inplace(); }
// @brief Ο(NlogN). FAST のみ
F &pow_inplace(long long k) {
int n = (*this).size(), l = 0;
assert(k >= 0);
if (!k) {
for (int i = 0; i < n; ++i)
(*this)[i] = !i;
return *this;
}
while (l < n and (*this)[l] == 0)
++l;
if (l > (n - 1) / k or l == n)
return *this = F(n);
T c = (*this)[l];
(*this).erase((*this).begin(), (*this).begin() + l);
(*this) /= c;
(*this).log_inplace();
(*this).resize(n - l * k);
(*this) *= k;
(*this).exp_inplace();
(*this) *= c.pow(k);
(*this).insert((*this).begin(), l * k, 0);
return *this;
}
// @brief Ο(NlogN). FAST のみ
F pow(const long long k) const { return F(*this).pow_inplace(k); }
// @brief Ο(NlogN). FAST のみ
F sqrt(int deg = -1) const {
auto SQRT = [&](T t) {
int mod = T::mod();
if (t == 0 or t == 1)
return t;
int v = (mod - 1) / 2;
if (t.pow(v) != 1)
return T(-1);
int q = mod - 1, m = 0;
while (~q & 1)
q >>= 1, m++;
std::mt19937 mt;
T z = mt();
while (z.pow(v) != mod - 1)
z = mt();
T c = z.pow(q), u = t.pow(q), r = t.pow((q + 1) / 2);
for (; m > 1; m--) {
T tmp = u.pow(1 << (m - 2));
if (tmp != 1)
r = r * c, u = u * c * c;
c = c * c;
}
return T(std::min(r.val(), mod - r.val()));
};
int n = (*this).size();
if (deg == -1)
deg = n;
if ((*this)[0] == 0) {
for (int i = 1; i < n; i++) {
if ((*this)[i] != 0) {
if (i & 1)
return F(0);
if (deg - i / 2 <= 0)
break;
auto ret = (*this);
ret >>= i;
ret.resize(n - i);
ret = ret.sqrt(deg - i / 2);
if (ret.empty())
return F(0);
ret <<= (i / 2);
ret.resize(deg);
return ret;
}
}
return F(deg);
}
auto sqr = SQRT((*this)[0]);
if (sqr * sqr != (*this)[0])
return F(0);
F ret{sqr};
T ti = T(1) / T(2);
for (int i = 1; i < deg; i <<= 1) {
auto u = (*this);
u.resize(i << 1);
ret = (ret.inv(i << 1) * u + ret) * ti;
}
ret.resize(deg);
return ret;
}
// WARNING: TODO
void sparse_pow(const int n, const int d, const T c, const int k);
void sparse_pow_inv(const int n, const int d, const T c, const int k);
void stirling_first(int n);
void stirling_second(int n);
std::vector<T> multipoint_evaluation(const std::vector<T> &p);
// @brief O(_MAX log n)
F &binomial_neg(int r, int d, int _MAX, BiCoef<T> &bc) {
REP(n, _MAX) { (*this)[n] = bc.com(n + d - 1, d - 1) * T(r).pow(n); }
return *this;
}
};
/* #endregion Math Formal Power Series */
/* #region barlekamp_massey_and_bostan_mori */
template <class F> F Berlekamp_Massey(const F &a) {
using T = typename F::value_type;
int n = a.size();
F c{-1}, c2{0};
T r2 = 1;
int i2 = -1;
for (int i = 0; i < n; i++) {
T r = 0;
int d = c.size();
for (int j = 0; j < d; j++)
r += c[j] * a[i - j];
if (r == 0)
continue;
T coef = -r / r2;
int d2 = c2.size();
if (d - i >= d2 - i2) {
for (int j = 0; j < d2; j++)
c[j + i - i2] += c2[j] * coef;
} else {
F tmp(c);
c.resize(d2 + i - i2);
for (int j = 0; j < d2; j++)
c[j + i - i2] += c2[j] * coef;
c2 = std::move(tmp);
i2 = i, r2 = r;
}
}
return {c.begin() + 1, c.end()};
}
// return generating function of a, s.t. F(x) = P(x) / Q(x)
template <class F> std::pair<F, F> find_generating_function(F a) {
auto q = Berlekamp_Massey(a);
int d = q.size();
a.resize(d);
q.insert(q.begin(), 1);
for (int i = 1; i < (int)q.size(); i++)
q[i] *= -1;
a *= q;
return {a, q};
}
// return [x^k] p(x) / q(x)
template <class T, Mode mode>
T compute_Kthterm(FormalPowerSeries<T, mode> p, FormalPowerSeries<T, mode> q,
long long k) {
int d = q.size();
assert(q[0] == 1 and p.size() + 1 <= d);
while (k) {
auto q_minus = q;
for (int i = 1; i < d; i += 2)
q_minus[i] *= -1;
p.resize(2 * d);
q.resize(2 * d);
p *= q_minus;
q *= q_minus;
for (int i = 0; i < d - 1; i++)
p[i] = p[(i << 1) | (k & 1)];
for (int i = 0; i < d; i++)
q[i] = q[i << 1];
p.resize(d - 1);
q.resize(d);
k >>= 1;
}
return p[0];
}
template <class T, Mode mode>
T compute_Kthterm(
std::pair<FormalPowerSeries<T, mode>, FormalPowerSeries<T, mode>> f,
long long k) {
return compute_Kthterm(f.first, f.second, k);
}
/* #endregion barlekamp_massey_and_bostan_mori */
using mint = modint1000000007;
using fps = FormalPowerSeries<mint, NAIVE>;
int p, q, r, K;
signed main() {
cin >> p >> q >> r >> K;
// https://yukicoder.me/submissions/655024
int n = 100000;
fps a(n, 1);
a[0] = p % 10, a[1] = q % 10, a[2] = r % 10;
FOR(ni, 3, n) {
a[ni] = (a[ni - 3].val() + a[ni - 2].val() + a[ni - 1].val()) % 10;
}
// REP(ni, n) { cerr << a[ni].val() << " "; }
// debug();
auto f = find_generating_function(a);
print(compute_Kthterm(f, K - 1).val() % 10);
}