2020-ccpc-weihai
G 线段树 区间修改、取模，区间哈希和查询
需要维护一个支持区间加1并对固定模数取模、区间哈希查询的线段树
开局就想写的一道题，写到最后艰难调出来后wa7，最终放弃上机辅助队友看别的题
晚上回去又调了很久，发现了几个错误
- 线段树哈希写错了，在求哈希和的时候不像普通的线段树区间和一样，查询哈希和时查询的区间[L, R]是需要动态变化的，必须保证
L被不断地截断，才能保证算法的正确性 - 眼睛比较瞎，前缀和pre[]对M(65536)取模了
- 最开始的purify(将那些超过65536的位置取模)写挫了，在终止条件(l == r)之前就调用了down函数。调了一年才发现原来是这里有问题：如果在终止条件之前就调用down函数，这会导致地址的越界访问。因为st只开了4倍空间，所以如果在那种边角叶子结点（在满二叉树上多一个节外生枝的结构）仍然尝试down下去，就会访问到8倍的位置！在CF居然没有发生RE报警，以至于我一度怀疑是自己算法写错了，其实是空间的计算错误导致了UKE。
1#define ls (p << 1)
2#define rs ((p << 1) | 1)
3#define mid ((l + r) >> 1)
4
5using namespace std;
6const int maxn = 5e5 + 10;
7const int M = 65536;
8
9const int pp = 999983;
10const int mod = 1000237529;
11
12int a[maxn];
13ll tag1[maxn << 2], st2[maxn << 2], st[maxn << 2];
14ll po[maxn], pre[maxn];
15
16void up(int p, int l, int r){
17 st[p] = st[ls] + st[rs] * po[mid - l + 1] % mod; st[p] %= mod;
18 st2[p] = max(st2[ls], st2[rs]);
19}
20
21void build(int p, int l, int r, int k, int x){
22 if(l == r && l == k){
23 st[p] = st2[p] = x;
24 return ;
25 }
26 if(k <= mid) build(ls, l, mid, k, x);
27 else build(rs, mid + 1, r, k, x);
28 up(p, l, r);
29}
30
31void down(int p, int l, int r){
32 if(tag1[p]){
33 tag1[ls] += tag1[p];
34 tag1[rs] += tag1[p];
35
36 st[ls] += pre[mid - l] * tag1[p] % mod; st[ls] %= mod;
37 st[rs] += pre[r - mid - 1] * tag1[p] % mod; st[rs] %= mod;
38
39 st2[ls] += tag1[p];
40 st2[rs] += tag1[p];
41
42 tag1[p] = 0;
43 }
44}
45
46void update(int p, int l, int r, int L, int R){
47 if(L <= l && r <= R){
48 st[p] += pre[r - l]; st[p] %= mod;
49 st2[p]++; tag1[p]++;
50 return ;
51 }
52 down(p, l, r);
53 if(L <= mid) udpate(ls, l, mid, L, R);
54 if(R > mid) update(rs, mid + 1, r, L ,R);
55 up(p, l, r);
56}
57
58void purify(int p, int l, int r){
59 if(st2[p] < M) return;
60 down(p, l, r);
61 if(l == r){
62 st[p] %= M; st2[p] %= M;
63 return ;
64 }
65
66 if(st2[ls] >= M) purify(ls, l, mid);
67 if(st2[rs] >= M) purify(rs, mid + 1, r);
68 up(p, l, r);
69}
70
71ll hsh(int p, int l, int r, int L, int R){
72 if(L <= l && r <= R) return st[p];
73 down(p, l, r);
74
75 if(R <= mid) return hsh(ls, l, mid, L, R);
76 else if(L > mid) return hsh(rs, mid + 1, r, L, R);
77 else{
78 ll ans = hsh(ls, l, mid, L, mid);
79 ans += hsh(rs, mid + 1, r, mid + 1, R) * po[mid - L + 1] % mod;
80 ans %= mod;
81 return ans;
82 }
83}
84
85int main(){
86// Fastin;
87 po[0] = 1;
88 for(int i = 1; i < maxn; i++) po[i] = po[i - 1] * 1ll * pp % mod;
89 pre[0] = 1;
90 for(int i = 1; i < maxn; i++) pre[i] = pre[i - 1] + po[i], pre[i] %= mod;
91
92 int n, m; scanf("%d %d", &n, &m);
93 for(int i = 1; i <= n; i++){
94 scanf("%d", a + i);
95 build(1, 1, n, i, a[i]);
96 }
97
98 while(m--){
99 int op; scanf("%d", &op);
100 if(op == 1){
101 int l, r; scanf("%d %d", &l, &r);
102 update(1, 1, n, l, r);
103 }
104 else{
105 int l, r, k; scanf("%d %d %d", &l, &r, &k);
106 purify(1, 1, n);
107
108 ll res1 = hsh(1, 1, n, l, l + k - 1);
109 ll res2 = hsh(1, 1, n, r, r + k - 1);
110 puts(res1 == res2? "yes": "no");
111 }
112 }
113
114 return 0;
115}L 分组背包 & LCM
给出n，构造某种拆分$p_1+p_2+…+p_k = n$，使得$lcm(p_1, p_2, …, p_k)$最大。
可以证明，当${p_i}$两两互素时，其lcm一定最大：
对于任意一组拆分，如果存在$gcd(a, b) = d>=2$，那么可以通过提取出d得到一个新的拆分方法，使得lcm不变，但是元素和变小。
另外，如果存在某个元素是若干素因子的乘积，也可以通过拆分该元素成若干的小数字，使得lcm不变、元素和变小。
通过上述两种更新得到后的新序列的情况一定不劣于原序列，那么不断进行这样的操作，最终一定会得到两两互素的序列。（这一点是显然的，因为上述两种操作均是单向的，且不可能构成环）
这样即可说明，两两互素的情况一定不会劣于任意的其他拆分方法。
那么分组背包，对素数进行分组，随便泡一下就过了。
1
2const int maxn = 3e4 + 10;
3int prime[maxn], top = 0, vis[maxn];
4void euler(){
5 for(int i = 2; i <= 30000; i++){
6 if(!vis[i]) prime[top++] = i;
7 for(int j = 0; j < top && prime[j] * i <= 30000; j++){
8 vis[prime[j] * i] = 1;
9 if(i % prime[j] == 0) break;
10 }
11 }
12}
13double dp[maxn], w[maxn];
14
15int main(){
16 // Fastin;
17
18 euler();
19 for(int i = 1; i <= 30000; i++) w[i] = log(i);
20
21 //遍历所有的组
22 for(int i = 0; i < top; i++){
23 for(int n = 30000; n >= 1; n--){
24 ll p = prime[i];
25 //用给定组中的所有物品来尝试更新当前重量。
26 while(p <= n){
27 dp[n] = max(dp[n], dp[n - p] + w[p]);
28 p *= prime[i];
29 }
30 }
31 }
32
33 TTT{
34 int n; scanf("%d", &n); printf("%.9f\n", dp[n]);
35 }
36 return 0;
37}