結果
問題 | No.1336 Union on Blackboard |
ユーザー |
![]() |
提出日時 | 2021-01-16 09:14:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 4,112 bytes |
コンパイル時間 | 2,128 ms |
コンパイル使用メモリ | 194,880 KB |
最終ジャッジ日時 | 2025-01-17 21:19:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }template <unsigned int mod> class modint {private:unsigned int v;static unsigned int norm(const unsigned int& x) { return x < mod ? x : x - mod; }static modint make(const unsigned int& x) {modint m;return m.v = x, m;}static modint inv(const modint& x) { return make(inverse(x.v, mod)); }static unsigned int inverse(int a, int m) {int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;while (*v) {t = *u / *v;swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]);}return (u[1] % m + m) % m;}public:modint() : v{0} {}modint(const long val) : v{norm(val % mod + mod)} {}modint(const modint<mod>& n) : v{n()} {}explicit operator bool() const noexcept { return v != 0; }bool operator!() const noexcept { return !static_cast<bool>(*this); }modint& operator=(const modint& n) { return v = n(), (*this); }modint& operator=(const long val) { return v = norm(val % mod + mod), (*this); }modint operator+() const { return *this; }modint operator-() const { return v == 0 ? make(0) : make(mod - v); }modint operator+(const modint& val) const { return make(norm(v + val())); }modint operator-(const modint& val) const { return make(norm(v + mod - val())); }modint operator*(const modint& val) const { return make((long)v * val() % mod); }modint operator/(const modint& val) const { return *this * inv(val); }modint& operator+=(const modint& val) { return *this = *this + val; }modint& operator-=(const modint& val) { return *this = *this - val; }modint& operator*=(const modint& val) { return *this = *this * val; }modint& operator/=(const modint& val) { return *this = *this / val; }modint operator+(const long val) const { return modint{v + val}; }modint operator-(const long val) const { return modint{v - val}; }modint operator*(const long val) const { return modint{(long)(v * (val % mod))}; }modint operator/(const long val) const { return modint{(long)v * inv(val)}; }modint& operator+=(const long val) { return *this = *this + val; }modint& operator-=(const long val) { return *this = *this - val; }modint& operator*=(const long val) { return *this = *this * val; }modint& operator/=(const long val) { return *this = *this / val; }bool operator==(const modint& val) const { return v == val.v; }bool operator!=(const modint& val) const { return !(*this == val); }bool operator==(const long val) const { return v == norm(val % mod + mod); }bool operator!=(const long val) const { return !(*this == val); }unsigned int operator()() const { return v; }friend modint operator+(const long val, const modint& n) { return n + val; }friend modint operator-(const long val, const modint& n) { return modint{val - n()}; }friend modint operator*(const long val, const modint& n) { return n * val; }friend modint operator/(const long val, const modint& n) { return modint{val} / n; }friend bool operator==(const long val, const modint& n) { return n == val; }friend bool operator!=(const long val, const modint& n) { return !(val == n); }friend istream& operator>>(istream& is, modint& n) {unsigned int v;return is >> v, n = v, is;}friend ostream& operator<<(ostream& os, const modint& n) { return (os << n()); }friend modint mod_pow(modint x, long n) {modint ans = 1;while (n) {if (n & 1) ans *= x;x *= x, n >>= 1;}return ans;}};constexpr int MOD = 1000000007;// constexpr int MOD = 998244353;using mint = modint<MOD>;signed main() {cin.tie(nullptr)->sync_with_stdio(false);int T;cin >> T;while (T--) {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++) cin >> A.at(i);mint ans = A.front();for (int i = 1; i < N; i++) {ans = ans + A.at(i) + ans * A.at(i);}cout << ans << '\n';}}