这场ACCODERS忘交，结果最后想起来匆匆只交了T1，然后文件名还没改，所以爆零了。。。
02表示法 100pts
高精度，不说了；
点击查看代码
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
string p[605];
string ans;
string p2[605];
string n;
string jia(string x, string y) {
string ans;
ans.clear();
for (int i = 1; i <= 205; i++) {
ans = ans + '0';
}
bool jin = false;
for (int i = 1; i <= 200; i++) {
int res = (x[i] - '0') + (y[i] - '0') + jin;
if (res >= 10) {
jin = true;
res %= 10;
} else {
jin = false;
}
ans[i] = res + '0';
}
return ans;
}
int cmp(string x, string y) {
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
for (int i = 1; i < x.size(); i++) {
if ((x[i] - '0') > (y[i] - '0')) return 1;
if ((x[i] - '0') < (y[i] - '0')) return 2;
}
return 0;
}
string jian(string x, string y) {
string ans;
ans.clear();
for (int i = 1; i <= 205; i++) {
ans = ans + '0';
}
for (int i = 1; i <= 200; i++) {
int xres = (x[i] - '0');
int yres = (y[i] - '0');
if (xres < yres) {
int pos = i;
for (int j = i + 1; j <= 200; j++) {
if ((x[j] - '0') > 0) {
x[j] = x[j] - 1;
pos = j;
break;
}
}
xres += 10;
for (int j = i + 1; j < pos; j++) x[j] = '9';
}
int now = xres - yres;
ans[i] = now + '0';
}
return ans;
}
int main() {
freopen("pow.in", "r", stdin);
freopen("pow.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
reverse(n.begin(), n.end());
n = '0' + n;
int now = n.size();
for (int j = now + 1; j <= 205; j++) {
n = n + '0';
}
for (int i = 0; i <= 600; i++) {
for (int j = 1; j <= 205; j++) {
p2[i] = p2[i] + '0';
}
}
p2[0][1] = '1';
for (int i = 1; i <= 600; i++) p2[i] = jia(p2[i - 1], p2[i - 1]);
p[0] = "0";
p[1] = "2(0)";
p[2] = "2";
p[3] = "2+2(0)";
p[4] = "2(2)";
for (int i = 5; i <= 600; i++) {
int x = i;
for (int j = 10; j >= 0; j--) {
if (x >= pow(2, j)) {
x -= pow(2, j);
if (p[i].empty()) {
if (j == 1) p[i] = "2";
else p[i] = "2(" + p[j] + ")";
} else {
if (j == 1) p[i] = p[i] + "+2";
else p[i] = p[i] + "+2(" + p[j] + ")";
}
}
}
}
for (int j = 600; j >= 0; j--) {
if (cmp(n, p2[j]) != 2) {
n = jian(n, p2[j]);
if (ans.empty()) {
if (j == 1) ans = "2";
else ans = "2(" + p[j] + ")";
} else {
if (j == 1) ans = ans + "+2";
else ans = ans + "+2(" + p[j] + ")";
}
}
}
cout << ans;
return 0;
}
子串的子串 70pts
暴力分挺足，70pts；
正解就是预处理 $ ans_{l, r} $ 代表答案，枚举每个子区间，然后如果有重复的就将这整个区间 $ -1 $；
考虑这样处理有什么好处，我们最后用二维前缀和倒序处理每个 $ ans $，这样我们就巧妙地去掉了所有重复的子区间且不会多减（这也是为什么不正序的原因）；
时间复杂度：$ \Theta(n^2 + q) $，注意要使用 $ Hash $ 判等；
点击查看代码
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
const unsigned long long pep = 229;
int n, q;
char s[5005];
unsigned long long h[5005], p[5005];
map<unsigned long long, int> mp;
int ans[5005][5005];
int main() {
freopen("substring.in", "r", stdin);
freopen("substring.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * pep;
h[i] = h[i - 1] * pep + s[i];
}
for (int len = 1; len <= n; len++) {
mp.clear();
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
unsigned long long now = h[r] - h[l - 1] * p[r - l + 1];
ans[mp[now]][r]--;
mp[now] = l;
}
}
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
ans[l][r] += ans[l + 1][r] + ans[l][r - 1] - ans[l + 1][r - 1] + 1;
}
}
int l, r;
for (int i = 1; i <= q; i++) {
cin >> l >> r;
cout << ans[l][r] << '\n';
}
return 0;
}
其实这题难点在于没有去想 $ \Theta(n^2 + q) $ 的做法，而是去想了 $ \Theta(nq) $ 的做法；
魔法咒语 -pts
赛时打T4，没写T3；
对于正解，我们正反向各建一棵 Trie，那么最原始的答案就是两个 Trie 的节点相乘；
但是有重的，考虑重复的原因在于一个串可能被划分两次；
比如abc 可以被划分成 a 和 bc，也可以被划分成 ab 和 c，对于这种情况，我们钦定划分点来自于前缀，这样就避免了；
具体实现上，我们遍历前缀树，对于每个节点，我们不统计其儿子在后缀树上的贡献，这样就去重了；
但是如果这个字符就是最后一个的话，按照原来的算法无法找到这个字符；
比如有 abc 和 c，找不到 abc；
但如果直接加 $ n $ 则可能会与之前拼接好的重复；
所以我们记一下每个串的结尾，然后如果是结尾加上即可；
但是如果原串长度为 $ 1 $，则无法被统计上，所以特判一下即可；
时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
int n;
string a[50005];
long long ans;
int tot1, tot2, cnt[28];
namespace Trie{
int son1[500005][28], son2[500005][28];
void add(string s, bool is) {
if (!is) {
int now = 0;
for (int i = 0; i < s.size(); i++) {
if (!son1[now][s[i] - 'a']) son1[now][s[i] - 'a'] = ++tot1;
now = son1[now][s[i] - 'a'];
}
} else {
int now = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (!son2[now][s[i] - 'a']) {
son2[now][s[i] - 'a'] = ++tot2;
cnt[s[i] - 'a']++;
}
now = son2[now][s[i] - 'a'];
}
}
}
}
using namespace Trie;
bool vis[28], vi[28];
int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
add(a[i], 1);
add(a[i], 0);
vis[a[i][a[i].size() - 1] - 'a'] = true;
if (a[i].size() == 1 && !vi[a[i][0] - 'a']) {
vi[a[i][0] - 'a'] = true;
ans++;
}
}
for (int i = 1; i <= tot1; i++) {
for (int j = 0; j <= 25; j++) {
if (!son1[i][j]) {
ans += cnt[j];
} else if (vis[j]) {
ans++;
}
}
}
cout << ans;
return 0;
}
表达式 35pts
乱打35pts；
暴力：我们可以用线段树来维护每个 $ x $ 对应的这些操作的结果，可以通过小模数的数据；
正解：发现题目中除暴力给出的模数都不是质数，且进行唯一分解定理得到的互质的数数量都不多，大小也不大；
所以进行拆分，然后得到一堆互质的数，我们分别算出对于每个数的每个 $ x $ 对应的结果，然后会得到一个同余方程组，用 $ CRT $ 求解即可；
也是复习了一下 $ CRT $；
时间复杂度：设 $ |p| $ 为分解出的互质的数的大小之和，则时间复杂度为 $ \Theta(|p| n \log n) $；
比较卡空间和时间；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
long long n, m, mod;
struct sss{
char s;
long long a;
}e[500005];
long long ksm(long long a, long long b, long long p) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long ret = exgcd(b, a % b, x, y);
long long o = x;
x = y;
y = o - a / b * y;
return ret;
}
long long w(long long x) {
for (int i = 1; i <= n; i++) {
if (e[i].s == '+') x = (x + e[i].a) % mod;
if (e[i].s == '*') x = (x * e[i].a) % mod;
if (e[i].s == '^') x = ksm(x, e[i].a, mod);
}
return x;
}
long long pri[500005], cnt, inv[500005];
namespace SEG{
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
long long l, r, val[8][31];
}tr[525005];
inline void push_up(int id) {
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < pri[i]; j++) {
tr[id].val[i][j] = tr[rs(id)].val[i][tr[ls(id)].val[i][j]];
}
}
}
inline void upd(int id, int x) {
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < pri[i]; j++) {
if (e[x].s == '+') {
tr[id].val[i][j] = (j + e[x].a) % pri[i];
}
if (e[x].s == '*') {
tr[id].val[i][j] = (j * e[x].a) % pri[i];
}
if (e[x].s == '^') {
tr[id].val[i][j] = ksm(j, e[x].a, pri[i]);
}
}
}
}
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
upd(id, l);
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
push_up(id);
}
void add(int id, int pos) {
if (tr[id].l == tr[id].r) {
upd(id, tr[id].l);
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (pos <= mid) add(ls(id), pos);
else add(rs(id), pos);
push_up(id);
}
}
int main() {
freopen("expr.in", "r", stdin);
freopen("expr.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
cin >> n >> m >> mod;
for (int i = 1; i <= n; i++) {
cin >> e[i].s;
cin >> e[i].a;
}
if (mod == 1) {
int s;
long long x;
int p;
char cc;
for (int i = 1; i <= m; i++) {
cin >> s;
if (s == 1) {
cin >> x;
cout << 0 << '\n';
}
if (s == 2) {
cin >> p;
cin >> cc;
cin >> x;
}
}
return 0;
}
if (t <= 3) {
int s;
long long x;
int p;
char cc;
for (int i = 1; i <= m; i++) {
cin >> s;
if (s == 1) {
cin >> x;
cout << w(x) << '\n';
}
if (s == 2) {
cin >> p;
cin >> cc;
cin >> x;
e[p].s = cc;
e[p].a = x;
}
}
return 0;
}
long long p = mod;
long long tx = 0, ty = 0;
for (int i = 2; i * i <= mod; i++) {
if (p % i == 0) {
long long y = 1;
while(p % i == 0) {
y *= i;
p /= i;
}
pri[++cnt] = y;
exgcd(mod / y, y, tx, ty);
inv[cnt] = (tx % y + y) % y;
}
}
if (p != 1) {
pri[++cnt] = p;
exgcd(mod / p, p, tx, ty);
inv[cnt] = (tx % p + p) % p;
}
SEG::bt(1, 1, n);
int s;
long long x;
int pp;
for (int i = 1; i <= m; i++) {
cin >> s;
if (s == 1) {
cin >> x;
long long ans = 0;
for (int i = 1; i <= cnt; i++) {
ans = (ans + mod / pri[i] * inv[i] % mod * SEG::tr[1].val[i][x % pri[i]] % mod) % mod;
}
cout << ans << '\n';
}
if (s == 2) {
cin >> pp;
cin >> e[pp].s;
cin >> e[pp].a;
SEG::add(1, pp);
}
}
return 0;
}