A
这题的本意是让更多人学习到浮点数会存在大数吃小数的情况，考察选手是否有良好的代码习惯。
某位选手的悲惨经历 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
i64 x, y;
cin >> x >> y;
if (x == 1)cout << 10 + y;
else if (x == 2)cout << i64(1e9) + y;
else cout << i64(1e18)+ y;
}
B
注意到往下走只有一次，考虑枚举在哪个位置往下走。
然后路径就是这样的：
考虑枚举这个分界点，假如交换分界点左边和右边的两列，会发现其实就是左边上面数字的贡献变成了下面数字，右边则是下面变成了上面，这个操作可以得到的最大收益是可以通过前缀与后缀计算的。
然后还有两种情况就是交界点和左边换，交界点和右边换。
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int T;
cin >> T;
while (T--) {
[&] {
int n;
cin >> n;
vector a(2, vector<int>(n + 1));
vector sum(2, vector<int>(n + 2));
for (int i = 0; i <= 1; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
if (n == 1) {
cout << a[0][1] + a[1][1] << endl;
return;
}
for (int i = 1; i <= n; i++)sum[0][i] = sum[0][i - 1] + a[0][i];
for (int i = n; i >= 1; i--)sum[1][i] = sum[1][i + 1] + a[1][i];
vector mx1(n + 1, -inf);
vector mx2(n + 2, -inf);
vector mx3(n + 1, -inf);
vector mx4(n + 2, -inf);
for (int i = 1; i <= n; i++) {
mx1[i] = max(mx1[i - 1], a[1][i]);
mx3[i] = max(mx3[i - 1], a[1][i] - a[0][i]);
}
for (int i = n; i >= 1; i--) {
mx2[i] = max(mx2[i + 1], a[0][i]);
mx4[i] = max(mx4[i + 1], a[0][i] - a[1][i]);
}
int ans = -inf;
for (int i = 1; i <= n; i++) {
ans = max(ans, sum[0][i] + sum[1][i]);
}
for (int i = 2; i < n; i++) {
ans = max(ans, sum[0][i] + sum[1][i] + mx3[i - 1] + mx4[i + 1]);
ans = max(ans, sum[0][i] + sum[1][i] - a[1][i] + mx1[i - 1]);
ans = max(ans, sum[0][i] + sum[1][i] - a[0][i] + mx2[i + 1]);
}
ans = max(ans, sum[0][1] + sum[1][1] + mx2[2] - a[0][1]);
ans = max(ans, sum[0][n] + sum[1][n] + mx1[n - 1] - a[1][n]);
cout << ans << endl;
}();
}
return 0;
}
C
对区间按照长度分类，然后发现相同长度的区间计算可以合并，。
。
然后考虑每个数可以是哪些长度区间的第一项，是哪些长度区间的第二项，这个可以使用前缀和快速计算。
假设数组 为 长度为
的斐波那契数列的第一项的和。
假设数组 为 长度为
的斐波那契数列的第二项的和。
然后枚举 的每一个元素，可以考虑这个元素对
的贡献和对
的贡献。
会发现贡献连续，所以可以差分计算。
时间复杂度 。
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int T;
cin >> T;
vector <Z> f(1000001);
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= 1000000; i++) {
f[i] = f[i - 1] + f[i - 2];
}
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1);
vector <Z> x(n + 1);
vector <Z> y(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
x[n - i + 1] += a[i];
y[i] += a[i];
}
for (int i = n - 1; i >= 1; i--)y[i] += y[i + 1];
for (int i = n - 1; i >= 1; i--)x[i] += x[i + 1];
Z ans = 0;
ans += x[1];
for (int i = 2; i <= n; i++) {
ans += x[i] * f[i - 2] + y[i] * f[i - 1];
}
cout << ans << endl;
}
return 0;
}
D
假如只有添加边，我们可以考虑用新增的边去更新全源最短路矩阵。
然后考虑如何处理删除操作。
对于这种操作难以撤销的问题，我们可以考虑把每次操作当做时间，建出线段树。
然后加边操作就相当于在时间轴的一段区间加边，最多覆盖 个区间，类似于懒标记永久化。
然后考虑如何处理询问。
先序遍历整颗线段树，到达一个节点就用覆盖这个区间的边去更新全源最短路矩阵。这里要注意，往下遍历叶子节点的时候传入的全源最短路矩阵参数不是引用。
显然询问是储存在叶子节点当中的，遍历到叶子节点就可以处理询问了。
因为每次加边操作会多logq个区间，每次更新是 时间复杂度，复制矩阵最多
次，每次时间复杂度
，总时间复杂度
。
// /## /## /## /###### /## /##
// | ## |__/ | ## /##__ ## | ## | ##
// | ## /## /## /## | ####### /###### /###### |__/ \ ## | ## | ##
// | ## | ## | ## | ## | ##__ ## |____ ## /##__ ## /######/ | ########
// | ## | ## | ## | ## | ## \ ## /####### | ## \ ## /##____/ |_____ ##
// | ## | ## | ## | ## | ## | ## /##__ ## | ## | ## | ## | ##
// | ## | ## | ######/ | ## | ## | ####### | ######/ | ######## | ##
// |__/ |__/ \______/ |__/ |__/ \_______/ \______/ |________/ |__/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
template<typename K, typename V, typename Comp = std::less<K>>
using ordered_map = __gnu_pbds::tree<K, V, Comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename K, typename Comp = std::less<K>>
using ordered_set = ordered_map<K, __gnu_pbds::null_type, Comp>;
using namespace __gnu_pbds;
using namespace std;
using i64 = long long;
using i128 = __int128;
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
#ifndef Liuhao
#define endl '\n'
#endif
#ifdef int
const int inf = 1e18;
#else
const int inf = 1e9;
#endif
const int mod = 998244353;
const int N = 500;
vector<array<int, 3>> node[N * 4];
int n, m, q;
int res[N];
#define mid ((l+r)/2)
void build(int p, int l, int r) {
node[p].clear();
if (l == r) {
return;
}
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
}
void upd(int p, int l, int r, int x, int y, const array<int, 3> &e) {
if (r < x || l > y)return;
if (x <= l && r <= y) {
node[p].push_back(e);
return;
}
if (x <= mid)upd(2 * p, l, mid, x, y, e);
if (y > mid)upd(2 * p + 1, mid + 1, r, x, y, e);
};
void que(int p, int l, int r, vector<vector<int>> dist) {
for (auto [x, y, w]: node[p]) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][x] + w + dist[y][j]);
dist[i][j] = min(dist[i][j], dist[i][y] + w + dist[x][j]);
}
}
}
if (l == r) {
if (res[l] == 1) {
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] != inf) {
ans = (ans + dist[i][j]) % mod;
}
}
}
cout << ans << endl;
}
return;
}
que(2 * p, l, mid, dist);
que(2 * p + 1, mid + 1, r, dist);
}
#undef mid
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int T;
cin >> T;
while (T--) {
cin >> n >> m >> q;
build(1, 1, q);
vector<array<int, 3>> edge(m + q + 1);
vector<int> st(m + 1 + q, 0);
vector<int> del(m + 1 + q, q);
for (int i = 1; i <= q; i++)res[i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
st[i] = 1;
}
int idx = m;
for (int c = 1; c <= q; c++) {
int op;
cin >> op;
if (op == 1) {
int u, v, w;
cin >> u >> v >> w;
edge[++idx] = {u, v, w};
st[idx] = c;
} else if (op == 2) {
int i;
cin >> i;
del[i] = c;
} else {
res[c] = 1;
}
}
vector dist(n + 1, vector<int>(n + 1, inf));
for (int i = 1; i <= n; i++)dist[i][i] = 0;
for (int c = 1; c <= idx; c++) {
if (st[c] == 1 && del[c] == q) {
auto [x, y, w] = edge[c];
dist[x][y] = dist[y][x] = min(dist[x][y], w);
} else upd(1, 1, q, st[c], del[c], edge[c]);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
que(1, 1, q, dist);
}
return 0;
}
E
首先介绍一个基于启发式合并的 做法。
很容易想到一个最普通的启发式合并的暴力方法。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<set<int>> sa(n + 1), sb(n + 1);
for (int i = 1, x; i <= n; i++) {
cin >> x;
sa[i].insert(x);
}
for (int i = 1, x; i <= n; i++) {
cin >> x;
sb[i].insert(x);
}
int q;
cin >> q;
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
int ans = 0;
for (auto i: sa[x]) {
if (sb[y].count(i))ans++;
}
cout << ans << '\n';
} else if (op == 2) {
if (sa[x].size() < sa[y].size()) {
sa[x].swap(sa[y]);
}
for (auto i: sa[y]) {
sa[x].insert(i);
}
} else {
if (sb[x].size() < sb[y].size()) {
sb[x].swap(sb[y]);
}
for (auto i: sb[y]) {
sb[x].insert(i);
}
}
}
}
}
这个代码肯定是会超时的，瓶颈在于查询部分，然后我们考虑如何优化一下这部分的时间复杂度。
注意到询问 答案不为
的
对数不是很多，是小于
的，所以我们考虑能不能在合并的过程中就把这些对的答案给维护出来。
然后就可以得到以下代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
vector<vector<int>> sa(n + 1), sb(n + 1);
for (int i = 1, x; i <= n; i++) {
cin >> x;
a[x] = i;
sa[i].push_back(x);
}
for (int i = 1, x; i <= n; i++) {
cin >> x;
b[x] = i;
sb[i].push_back(x);
}
map<pair<int, int>, int> mp;
for (int i = 1; i <= n; i++) mp[{a[i], b[i]}]++;
int q;
cin >> q;
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
cout << mp[{x, y}] << '\n';
} else if (op == 2) {
for (auto i: sa[y]) {
sa[x].push_back(i);
mp[{a[i], b[i]}]--;
a[i] = x;
mp[{a[i], b[i]}]++;
}
} else {
for (auto i: sb[y]) {
sb[x].push_back(i);
mp[{a[i], b[i]}]--;
b[i] = x;
mp[{a[i], b[i]}]++;
}
}
}
}
}
这份代码虽然查询部分更快了，但是合并部分又失去了启发式合并的性质。
那我们能不能像之前一样，判断 size，将小集合合并到大集合呢？
假如直接交换的话是会错的，这是因为即使集合交换了，但是上面的 a 数组和 b 数组没有更新，指向的还是原来的集合，这时候就可以用辅助数组，存真实的集合编号，这样就可以进行交换了。
修改后得到以下代码。
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1), ida(n + 1), idb(n + 1);
vector<vector<int>> sa(n + 1), sb(n + 1);
iota(ida.begin(), ida.end(), 0);
iota(idb.begin(), idb.end(), 0);
for (int i = 1, x; i <= n; i++) {
cin >> x;
a[x] = i;
sa[i].push_back(x);
}
for (int i = 1, x; i <= n; i++) {
cin >> x;
b[x] = i;
sb[i].push_back(x);
}
map<pair<int, int>, int> mp;
for (int i = 1; i <= n; i++) mp[{a[i], b[i]}]++;
int q;
cin >> q;
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
cout << mp[{ida[x], idb[y]}] << '\n';
} else if (op == 2) {
if (sa[x].size() < sa[y].size()) {
sa[x].swap(sa[y]);
swap(ida[x], ida[y]);
}
for (auto i: sa[y]) {
sa[x].push_back(i);
mp[{a[i], b[i]}]--;
a[i] = ida[x];
mp[{a[i], b[i]}]++;
}
} else {
if (sb[x].size() < sb[y].size()) {
sb[x].swap(sb[y]);
swap(idb[x], idb[y]);
}
for (auto i: sb[y]) {
sb[x].push_back(i);
mp[{a[i], b[i]}]--;
b[i] = idb[x];
mp[{a[i], b[i]}]++;
}
}
}
}
}
接下来介绍一个基于二维数点的 离线做法。
首先将 Alice 集合和 Bob 集合合并的过程建出一颗树，最终可能会不联通，所以最后要把单独的集合都连起来。
如样例：
Alice 集合合并过程
Bob 集合合并过程
然后问题就简单了，每次查询都可以转化到这两个树上的两棵子树所包含叶子编号的交集问题。
比如最后一次查询，1 5 1 可以转化为 Alice 以 7 为根的子树与 Bob 以 7 为根的子树的交集。
子树交集问题可以用二维数点解决。
考虑如何建树，每合并一次就在树上新增一个节点，用并查集合并儿子，由于合并操作最多 次，所以树上的节点最多
个。
然后考虑如何查询，可以发现每个查询可以分别唯一的对应到树上的节点。
然后问题就转化为了子树颜色求交集的问题。
考虑使用 序维护树上颜色。
将两颗树都转化为 序。
然后查询可以转换为 两个区间相同的颜色数量。
可以使用二维数点矩形求和解决。
代码如下：
// /## /## /## /###### /## /##
// | ## |__/ | ## /##__ ## | ## | ##
// | ## /## /## /## | ####### /###### /###### |__/ \ ## | ## | ##
// | ## | ## | ## | ## | ##__ ## |____ ## /##__ ## /######/ | ########
// | ## | ## | ## | ## | ## \ ## /####### | ## \ ## /##____/ |_____ ##
// | ## | ## | ## | ## | ## | ## /##__ ## | ## | ## | ## | ##
// | ## | ## | ######/ | ## | ## | ####### | ######/ | ######## | ##
// |__/ |__/ \______/ |__/ |__/ \_______/ \______/ |________/ |__/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
template<typename K, typename V, typename Comp = std::less<K>>
using ordered_map = __gnu_pbds::tree<K, V, Comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename K, typename Comp = std::less<K>>
using ordered_set = ordered_map<K, __gnu_pbds::null_type, Comp>;
using namespace __gnu_pbds;
using namespace std;
using i64 = long long;
using i128 = __int128;
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
#ifndef Liuhao
#define endl '\n'
#endif
#ifdef int
const int inf = 1e18;
#else
const int inf = 1e9;
#endif
struct DSU {
vector<int> f, siz;
explicit DSU(int n) : f(n + 1), siz(n + 1, 1) {
iota(f.begin(), f.end(), 0);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
struct Fenwick {
int n{};
vector<int> tr;
Fenwick(int n_) : n(n_), tr(n + 1) {}
void add(int x, int y) {
while (x <= n)tr[x] += y, x += x & -x;
}
int sum(int x) {
int res = 0;
while (x)res += tr[x], x -= x & -x;
return res;
}
int operator[](int x) {
return sum(x) - sum(x - 1);
}
int operator()(int l, int r) {
return sum(r) - sum(l - 1);
}
};
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int T;
cin >> T;
int sum = 0;
int sumq = 0;
while (T--) {
int n;
cin >> n;
sum += n;
vector<int> a(n + 1);
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
int q;
cin >> q;
sumq += q;
vector<PII > que;
vector<vector<int>> g1(n + 1);
vector<vector<int>> g2(n + 1);
DSU d1(n + n + 1);
DSU d2(n + n + 1);
auto merge1 = [&](int x, int y) {
g1.emplace_back();
g1.back().push_back(d1.find(x));
g1.back().push_back(d1.find(y));
d1.merge(g1.size() - 1, x);
d1.merge(g1.size() - 1, y);
};
auto merge2 = [&](int x, int y) {
g2.emplace_back();
g2.back().push_back(d2.find(x));
g2.back().push_back(d2.find(y));
d2.merge(g2.size() - 1, x);
d2.merge(g2.size() - 1, y);
};
for (int c = 1; c <= q; c++) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
que.push_back({d1.find(x), d2.find(y)});
} else if (op == 2) {
merge1(x, y);
} else {
merge2(x, y);
}
}
for (int i = 2; i <= n; i++) {
if (!d1.same(i, i - 1))merge1(i - 1, i);
if (!d2.same(i, i - 1))merge2(i - 1, i);
}
int n1 = g1.size() - 1;
int n2 = g2.size() - 1;
vector<int> dfn1(n1 + 1);
vector<int> id1(n1 + 1);
vector<int> size1(n1 + 1);
vector<int> dfn2(n2 + 1);
vector<int> id2(n2 + 1);
vector<int> size2(n2 + 1);
vector<int> st(n + 1);
int cnt1 = 0;
int cnt2 = 0;
auto dfs1 = [&](auto &&self, int x) -> void {
dfn1[++cnt1] = x;
if (x <= n)st[a[x]] = cnt1;
id1[x] = cnt1;
size1[x]++;
for (auto i: g1[x]) {
self(self, i);
size1[x] += size1[i];
}
};
dfs1(dfs1, n1);
auto dfs2 = [&](auto &&self, int x) -> void {
dfn2[++cnt2] = x;
id2[x] = cnt2;
size2[x]++;
for (auto i: g2[x]) {
self(self, i);
size2[x] += size2[i];
}
};
dfs2(dfs2, n2);
vector<vector<array<int, 3>>> f(n2 + 1);
vector<int> ans(que.size());
for (int i = 0; i < que.size(); i++) {
auto [x, y] = que[i];
if (id2[y] - 1) {
f[id2[y] - 1].push_back({x, -1, i});
}
f[id2[y] + size2[y] - 1].push_back({x, 1, i});
}
Fenwick arr(n1 + 1);
for (int i = 1; i <= n2; i++) {
if (dfn2[i] <= n)arr.add(st[b[dfn2[i]]], 1);
for (auto [x, flag, j]: f[i]) {
int l = id1[x];
int r = id1[x] + size1[x] - 1;
ans[j] += flag * (arr.sum(r) - arr.sum(l - 1));
}
}
for (auto i: ans)cout << i << endl;
}
return 0;
}
F
考虑使用一颗线段树维护a序列和b序列。
我们要维护的信息组成的矩阵有
人力去考虑这些元素之间的转移太过麻烦，考虑到操作中的运算都是线性运算，所以可以使用矩阵代表懒标记，这样我们只需要构造出加所代表的矩阵和乘所代表的矩阵，懒标记行和懒标记合并只需要新懒标记左乘到右懒标记即可。
现在先考虑如何构造加所代表的懒标记。
然后考虑如何构造乘所代表的懒标记
最后考虑将 累加到
的操作
每次操作之后对 [1,n]区间进行 操作
完成所有操作查询结果即可。
不展开矩阵乘法也可以通过。
// /## /## /## /###### /## /##
// | ## |__/ | ## /##__ ## | ## | ##
// | ## /## /## /## | ####### /###### /###### |__/ \ ## | ## | ##
// | ## | ## | ## | ## | ##__ ## |____ ## /##__ ## /######/ | ########
// | ## | ## | ## | ## | ## \ ## /####### | ## \ ## /##____/ |_____ ##
// | ## | ## | ## | ## | ## | ## /##__ ## | ## | ## | ## | ##
// | ## | ## | ######/ | ## | ## | ####### | ######/ | ######## | ##
// |__/ |__/ \______/ |__/ |__/ \_______/ \______/ |________/ |__/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
template<typename K, typename V, typename Comp = std::less<K>>
using ordered_map = __gnu_pbds::tree<K, V, Comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename K, typename Comp = std::less<K>>
using ordered_set = ordered_map<K, __gnu_pbds::null_type, Comp>;
using namespace __gnu_pbds;
using namespace std;
using i64 = long long;
using i128 = __int128;
#define PII pair<int,int>
#define fi first
#define se second
#ifndef Liuhao
#define endl '\n'
#endif
#ifdef int
const int inf = 1e18;
#else
const int inf = 1e9;
#endif
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// TODO: Dynamic ModInt
template<typename T>
constexpr T power(T a, u64 b) {
T res{1};
for (; b != 0; b /= 2, a *= a) {
if (b % 2 == 1) {
res *= a;
}
}
return res;
}
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
return 1ULL * a * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
template<typename U, U P>
struct ModIntBase {
public:
constexpr ModIntBase() : x(0) {}
template<typename T>
constexpr ModIntBase(T x_) : x(norm(x_ % T{P})) {}
constexpr static U norm(U x) {
if ((x >> (8 * sizeof(U) - 1) & 1) == 1) { x += P; }
if (x >= P) { x -= P; }
return x;
}
constexpr U val() const { return x; }
constexpr ModIntBase operator-() const {
ModIntBase res;
res.x = norm(P - x);
return res;
}
constexpr ModIntBase inv() const { return power(*this, P - 2); }
constexpr ModIntBase &operator*=(const ModIntBase &rhs) &{
x = mulMod<P>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) &{
x = norm(x + rhs.x);
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) &{
x = norm(x - rhs.x);
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) &{ return *this *= rhs.inv(); }
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) { return os << a.val(); }
friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) { return lhs.val() == rhs.val(); }
friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) { return lhs.val() != rhs.val(); }
friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) { return lhs.val() < rhs.val(); }
private:
U x{};
};
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
constexpr u32 P = 998244353;
using Z = ModInt<P>;
Z tmp[7][7]{};
struct Tag {
Z a[7][7]{{1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1}};
int flag = 0;
void app(const Tag &t) {
tmp[0][0] = t.a[0][0] * a[0][0];
tmp[0][1] = t.a[0][0] * a[0][1] + t.a[0][1] * a[1][1];
tmp[0][2] = t.a[0][0] * a[0][2] + t.a[0][1] * a[1][2] + t.a[0][2] * a[2][2];
tmp[0][3] = t.a[0][0] * a[0][3] + t.a[0][1] * a[1][3] + t.a[0][2] * a[2][3] + t.a[0][3] * a[3][3];
tmp[0][4] =
t.a[0][0] * a[0][4] + t.a[0][1] * a[1][4] + t.a[0][2] * a[2][4] + t.a[0][3] * a[3][4] + t.a[0][4] * a[4][4];
tmp[0][5] =
t.a[0][0] * a[0][5] + t.a[0][1] * a[1][5] + t.a[0][2] * a[2][5] + t.a[0][3] * a[3][5] + t.a[0][4] * a[4][5] +
t.a[0][5] * a[5][5];
tmp[0][6] =
t.a[0][0] * a[0][6] + t.a[0][1] * a[1][6] + t.a[0][2] * a[2][6] + t.a[0][3] * a[3][6] + t.a[0][4] * a[4][6] +
t.a[0][5] * a[5][6] + t.a[0][6] * a[6][6];
tmp[1][1] = t.a[1][1] * a[1][1];
tmp[1][2] = t.a[1][1] * a[1][2] + t.a[1][2] * a[2][2];
tmp[1][3] = t.a[1][1] * a[1][3] + t.a[1][2] * a[2][3] + t.a[1][3] * a[3][3];
tmp[1][4] = t.a[1][1] * a[1][4] + t.a[1][2] * a[2][4] + t.a[1][3] * a[3][4] + t.a[1][4] * a[4][4];
tmp[1][5] =
t.a[1][1] * a[1][5] + t.a[1][2] * a[2][5] + t.a[1][3] * a[3][5] + t.a[1][4] * a[4][5] + t.a[1][5] * a[5][5];
tmp[1][6] =
t.a[1][1] * a[1][6] + t.a[1][2] * a[2][6] + t.a[1][3] * a[3][6] + t.a[1][4] * a[4][6] + t.a[1][5] * a[5][6] +
t.a[1][6] * a[6][6];
tmp[2][2] = t.a[2][2] * a[2][2];
tmp[2][3] = t.a[2][2] * a[2][3] + t.a[2][3] * a[3][3];
tmp[2][4] = t.a[2][2] * a[2][4] + t.a[2][3] * a[3][4] + t.a[2][4] * a[4][4];
tmp[2][5] = t.a[2][2] * a[2][5] + t.a[2][3] * a[3][5] + t.a[2][4] * a[4][5] + t.a[2][5] * a[5][5];
tmp[2][6] =
t.a[2][2] * a[2][6] + t.a[2][3] * a[3][6] + t.a[2][4] * a[4][6] + t.a[2][5] * a[5][6] + t.a[2][6] * a[6][6];
tmp[3][3] = t.a[3][3] * a[3][3];
tmp[3][4] = t.a[3][3] * a[3][4] + t.a[3][4] * a[4][4];
tmp[3][5] = t.a[3][3] * a[3][5] + t.a[3][4] * a[4][5] + t.a[3][5] * a[5][5];
tmp[3][6] = t.a[3][3] * a[3][6] + t.a[3][4] * a[4][6] + t.a[3][5] * a[5][6] + t.a[3][6] * a[6][6];
tmp[4][4] = t.a[4][4] * a[4][4];
tmp[4][5] = t.a[4][4] * a[4][5] + t.a[4][5] * a[5][5];
tmp[4][6] = t.a[4][4] * a[4][6] + t.a[4][5] * a[5][6] + t.a[4][6] * a[6][6];
tmp[5][5] = t.a[5][5] * a[5][5];
tmp[5][6] = t.a[5][5] * a[5][6] + t.a[5][6] * a[6][6];
tmp[6][6] = t.a[6][6] * a[6][6];
a[0][0] = tmp[0][0];
a[0][1] = tmp[0][1];
a[0][2] = tmp[0][2];
a[0][3] = tmp[0][3];
a[0][4] = tmp[0][4];
a[0][5] = tmp[0][5];
a[0][6] = tmp[0][6];
a[1][1] = tmp[1][1];
a[1][2] = tmp[1][2];
a[1][3] = tmp[1][3];
a[1][4] = tmp[1][4];
a[1][5] = tmp[1][5];
a[1][6] = tmp[1][6];
a[2][2] = tmp[2][2];
a[2][3] = tmp[2][3];
a[2][4] = tmp[2][4];
a[2][5] = tmp[2][5];
a[2][6] = tmp[2][6];
a[3][3] = tmp[3][3];
a[3][4] = tmp[3][4];
a[3][5] = tmp[3][5];
a[3][6] = tmp[3][6];
a[4][4] = tmp[4][4];
a[4][5] = tmp[4][5];
a[4][6] = tmp[4][6];
a[5][5] = tmp[5][5];
a[5][6] = tmp[5][6];
a[6][6] = tmp[6][6];
flag = 1;
}
};
vector<Tag> tag;
struct Node {
Z a[7][1];
void app(const Tag &t) {
tmp[0][0] =
t.a[0][0] * a[0][0] + t.a[0][1] * a[1][0] + t.a[0][2] * a[2][0] + t.a[0][3] * a[3][0] + t.a[0][4] * a[4][0] +
t.a[0][5] * a[5][0] + t.a[0][6] * a[6][0];
tmp[1][0] =
t.a[1][1] * a[1][0] + t.a[1][2] * a[2][0] + t.a[1][3] * a[3][0] + t.a[1][4] * a[4][0] + t.a[1][5] * a[5][0] +
t.a[1][6] * a[6][0];
tmp[2][0] =
t.a[2][2] * a[2][0] + t.a[2][3] * a[3][0] + t.a[2][4] * a[4][0] + t.a[2][5] * a[5][0] + t.a[2][6] * a[6][0];
tmp[3][0] = t.a[3][3] * a[3][0] + t.a[3][4] * a[4][0] + t.a[3][5] * a[5][0] + t.a[3][6] * a[6][0];
tmp[4][0] = t.a[4][4] * a[4][0] + t.a[4][5] * a[5][0] + t.a[4][6] * a[6][0];
tmp[5][0] = t.a[5][5] * a[5][0] + t.a[5][6] * a[6][0];
tmp[6][0] = t.a[6][6] * a[6][0];
a[0][0] = tmp[0][0];
a[1][0] = tmp[1][0];
a[2][0] = tmp[2][0];
a[3][0] = tmp[3][0];
a[4][0] = tmp[4][0];
a[5][0] = tmp[5][0];
a[6][0] = tmp[6][0];
}
};
Node operator+(const Node &x, const Node &y) {
Node c;
for (int i = 0; i < 7; i++) {
c.a[i][0] = x.a[i][0] + y.a[i][0];
}
return c;
}
vector<Node> node;
void app(int p, const Tag &v) {
tag[p].app(v);
node[p].app(v);
}
void pushdown(int p) {
if (!tag[p].flag)return;
app(2 * p, tag[p]);
app(2 * p + 1, tag[p]);
tag[p] = Tag();
}
#define mid ((l+r)/2)
void upd(int p, int l, int r, int x, int y, const Tag &v) {
if (r < x || l > y)return;
if (x <= l && r <= y) {
app(p, v);
return;
}
pushdown(p);
upd(2 * p, l, mid, x, y, v);
upd(2 * p + 1, mid + 1, r, x, y, v);
node[p] = node[2 * p] + node[2 * p + 1];
}
void que(int p, int l, int r) {
if (l == r) {
cout << node[p].a[0][0] << ' ';
return;
}
pushdown(p);
que(2 * p, l, mid);
que(2 * p + 1, mid + 1, r);
}
vector<Node> aa;
void build(int p, int l, int r) {
if (l == r) {
node[p] = aa[l];
return;
}
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
node[p] = node[2 * p] + node[2 * p + 1];
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int n, m;
cin >> n >> m;
tag.resize(4 * n);
node.resize(4 * n);
aa.resize(n + 1);
for (int i = 1; i <= n; i++) {
int y;
cin >> y;
Z x = y;
aa[i] = Node{{{0}, {x * x * x * x * x}, {x * x * x * x}, {x * x * x}, {x * x}, {x}, {1}}};
}
build(1, 1, n);
for (int c = 1; c <= m; c++) {
int op;
cin >> op;
int l, r, y;
cin >> l >> r >> y;
Z x = y;
if (op == 1) {
upd(1, 1, n, l, r, {{{1, 0, 0, 0, 0, 0, 0},
{0, 1, 5 * x, 10 * x * x, 10 * x * x * x, 5 * x * x * x * x, x * x * x * x * x},
{0, 0, 1, 4 * x, 6 * x * x, 4 * x * x * x, x * x * x * x},
{0, 0, 0, 1, 3 * x, 3 * x * x, x * x * x},
{0, 0, 0, 0, 1, 2 * x, x * x},
{0, 0, 0, 0, 0, 1, x},
{0, 0, 0, 0, 0, 0, 1}
}, 1}
);
} else {
upd(1, 1, n, l, r, {{{1, 0, 0, 0, 0, 0, 0},
{0, x * x * x * x * x, 0, 0, 0, 0, 0},
{0, 0, x * x * x * x, 0, 0, 0, 0},
{0, 0, 0, x * x * x, 0, 0, 0},
{0, 0, 0, 0, x * x, 0, 0},
{0, 0, 0, 0, 0, x, 0},
{0, 0, 0, 0, 0, 0, 1}}, 1});
}
upd(1, 1, n, 1, n, {{{1, 1, 1, 1, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1}}, 1});
}
que(1, 1, n);
return 0;
}
矩阵乘法展开的代码实现：
# 矩阵格式，a * b, 表示每个元素是否可能非零
a = [[1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1],
]
b = [[1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1],
]
name = ["a", "t.a", "a"]
give = []
mod = 1 # 是否取模
f = open("out.txt", 'w')
for i in range(len(a)):
for j in range(len(b[0])):
s = ""
if mod: s += "("
flag = 0
for k in range(len(a[0])):
if a[i][k] == 0 or b[k][j] == 0: continue
s += f"{name[1]}[{i}][{k}]*{name[2]}[{k}][{j}]"
flag = 1
if mod: s += "%mod"
s += "+"
if not flag: continue
s = s[:-1]
if mod: s += ")%mod"
s += ';'
s = f"tmp[{i}][{j}]=" + s
print(s)
f.write(s + '\n')
give.append(f"{name[0]}[{i}][{j}]=tmp[{i}][{j}];")
for i in give:
print(i)
f.write(i + '\n')
京公网安备 11010502036488号