CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Sum of Powers
#include <bits/stdc++.h>
using namespace std;
vector<string> s;
void f(int n, int k)
{
if (n > k)
{
cout << s[n - 1];
return;
}
f(n - 1, k), f(n - 1, k);
}
int main(void)
{
for (int n, k; ~scanf("%d%d", &n, &k);)
{
s.assign(1, "AB");
for (int i = 1; i < n; ++i)
{
s.push_back(s.back());
for (int j = 0; j < s[i - 1].size(); ++j)
s[i].push_back(s[i - 1][j] == 'A' ? 'B' : 'A');
}
f(n, k);
}
}
Dot Product
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NPOS = -1;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a < M ? a : (a -= M); } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
/*
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
ll mul(ll a, ll b) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
*/
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数
/*
ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
{
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1; //return pow(a, phi(M) - 1);
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
*/
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
} M(1e9 + 7);
struct SegmentTree
{
struct Seg
{
int l, r;
ll suma, sumb, ans;
void upd(ll bdd, ll add)
{
M.qadd(ans, M.mul(sumb, add));
M.qadd(suma, M.mul(r - l + 1, add));
M.qadd(ans, M.mul(suma, bdd));
M.qadd(sumb, M.mul(r - l + 1, bdd));
}
friend Seg up(const Seg &lc, const Seg &rc)
{
Seg fa = lc;
fa.r = rc.r;
M.qadd(fa.suma, rc.suma);
M.qadd(fa.sumb, rc.sumb);
M.qadd(fa.ans, rc.ans);
return fa;
}
};
struct Node : Seg
{
int lc, rc;
ll bdd, add;
};
vector<Node> v;
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r)
{
int rt = v.size();
v.push_back({});
v[rt].Seg::operator=({l, r, 0, 0, 0});
v[rt].lc = v[rt].rc = NPOS;
v[rt].bdd = 0, v[rt].add = 0;
}
void down(int rt)
{
int m = v[rt].l + v[rt].r >> 1;
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].l, m);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].r);
upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].bdd, v[rt].add, v[rt].lc);
upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].bdd, v[rt].add, v[rt].rc);
v[rt].bdd = 0, v[rt].add = 0;
}
void upd(int l, int r, ll bdd, ll add, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return M.qadd(v[rt].bdd, bdd), M.qadd(v[rt].add, add), v[rt].upd(bdd, add);
down(rt);
if (r <= v[v[rt].lc].r)
upd(l, r, bdd, add, v[rt].lc);
else if (l >= v[v[rt].rc].l)
upd(l, r, bdd, add, v[rt].rc);
else
upd(l, v[v[rt].lc].r, bdd, add, v[rt].lc), upd(v[v[rt].rc].l, r, bdd, add, v[rt].rc);
v[rt].Seg::operator=(up(v[v[rt].lc], v[v[rt].rc]));
}
Seg ask(int l, int r, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt];
down(rt);
if (r <= v[v[rt].lc].r)
return ask(l, r, v[rt].lc);
if (l >= v[v[rt].rc].l)
return ask(l, r, v[rt].rc);
return up(ask(l, v[v[rt].lc].r, v[rt].lc), ask(v[v[rt].rc].l, r, v[rt].rc));
}
};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
SegmentTree t(1, n);
for (int i = 0, l, r, x; i < m; ++i)
{
char s[9];
scanf("%s%d%d", s, &l, &r);
if (s[0] == '?')
printf("%lld\n", t.ask(l, r).ans);
else
scanf("%d", &x), t.upd(l, r, s[0] != '*' ? x : 0, s[0] == '*' ? x : 0);
}
}