Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll MOD = 1000 * 1000 * 1000 + 7;
- ll madd(ll a, ll b) {
- a += b;
- if (a >= MOD)
- a -= MOD;
- return a;
- }
- ll mmul(ll a, ll b) {
- return a * b % MOD;
- }
- struct Triple {
- ll a, b, c;
- explicit Triple(ll a_ = 0, ll b_ = 0, ll c_ = 0): a(a_ % MOD), b(b_ % MOD), c(c_ % MOD) {}
- Triple operator+(const Triple& t) const {
- return Triple(madd(a, t.a), madd(b, t.b), madd(c, t.c));
- }
- };
- struct Node {
- ll f[2][2];
- Node() {
- f[0][0] = f[0][1] = f[1][0] = f[1][1] = 0;
- }
- Node(const Triple& t): Node() {
- f[0][0] = t.b;
- f[0][1] = t.c;
- f[1][0] = t.a;
- }
- };
- Node unite(const Node& l, const Node& r) {
- Node res;
- for (int resL = 0; resL < 2; resL++)
- for (int resR = 0; resR < 2; resR++)
- for (int mid = 0; mid < 2; mid++)
- res.f[resL][resR] = madd(res.f[resL][resR], mmul(l.f[resL][mid], r.f[mid][resR]));
- return res;
- }
- struct Tree {
- int size;
- vector<Node> t;
- vector<Triple> data;
- Tree(int n): size(n), t(4 * n + 10), data(4 * n + 10) {}
- ll get() const {
- return t[0].f[0][0];
- }
- void upd(int i, int tl, int tr, int pos, const Triple& add) {
- if (tl == tr) {
- data[i] = data[i] + add;
- t[i] = Node(data[i]);
- return;
- }
- int m = (tl + tr) / 2;
- if (pos <= m)
- upd(2 * i + 1, tl, m, pos, add);
- else
- upd(2 * i + 2, m + 1, tr, pos, add);
- t[i] = unite(t[2 * i + 1], t[2 * i + 2]);
- }
- void upd(int pos, const Triple& add) {
- upd(0, 0, size - 1, pos, add);
- }
- };
- vector<ll> gen(int n, ll x, ll a, ll b, ll c, ll add) {
- vector<ll> res(n);
- res[0] = x;
- for (int i = 1; i < n; i++)
- res[i] = (a * res[i - 1] + b) % c + add;
- return res;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- Tree tree(n);
- ll w0, aw, bw;
- cin >> w0 >> aw >> bw;
- vector<ll> w = gen(m, w0, aw, bw, n, 1);
- ll d0, ad, bd;
- cin >> d0 >> ad >> bd;
- vector<ll> d = gen(m, d0, ad, bd, 3, 0);
- vector<ll> z(m);
- for (int i = 0; i < m; i++)
- z[i] = max(1ll, min(ll(n), w[i] + d[i] - 1));
- ll s0, as, bs;
- cin >> s0 >> as >> bs;
- vector<ll> s = gen(m, s0, as, bs, 1000 * 1000 * 1000, 1);
- for (int i = 0; i < n; i++)
- tree.upd(i, Triple(0, 1, 0));
- assert (tree.get() == 1);
- ll res = 0;
- for (int i = 0; i < m; i++) {
- Triple cur;
- if (w[i] - z[i] == 1)
- cur.a = s[i];
- else if (w[i] == z[i])
- cur.b = s[i];
- else if (w[i] - z[i] == -1)
- cur.c = s[i];
- else
- assert (false);
- tree.upd(w[i] - 1, cur);
- res = madd(res, tree.get());
- }
- cout << res << endl;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(nullptr);
- int tt;
- cin >> tt;
- for (int t = 1; t <= tt; t++) {
- cout << "Case #" << t << ": ";
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement