Rank 不重要了
A. 挤压
你说的对，期望怎么能算签呢？
一个重要的性质：一个数的平方可以在二进制下表示为 \(\sum_{i,j}\ s_i\ s_j\ 2^{i+j}\)，所以就可以分别求每一位对答案的贡献了。
设 \(f_{i,1/0,1/0}\) 表示到第 \(i\) 个数我们枚举的两位分别是 1/0 的方案数，简单 dp 一下即可，复杂度 \(\mathcal{O(n\log^2n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
ll a[N], f[N][2][2], ans, p[N];
namespace Wisadel
{ll Wqp(ll x, int y){ll res = 1;while(y){if(y & 1) res = res * x % mod; x = x * x % mod, y >>= 1;}return res;}short main(){freopen("a.in", "r", stdin) , freopen("a.out", "w", stdout);n = qr;ll zc = Wqp(1000000000, mod - 2);fo(i, 1, n) a[i] = qr;fo(i, 1, n) p[i] = qr, p[i] = p[i] * zc % mod;fo(i, 0, 29) fo(j, 0, 29){f[0][0][0] = 1, f[0][0][1] = f[0][1][0] = f[0][1][1] = 0;fo(k, 1, n) fo(x, 0, 1) fo(y, 0, 1){f[k][x][y] = f[k - 1][x][y] * (1 + mod - p[k]) % mod;bool A = a[k] & (1 << i), B = a[k] & (1 << j);int aa = x ^ (A ? 1 : 0), bb = y ^ (B ? 1 : 0);f[k][x][y] = (f[k][x][y] + f[k - 1][aa][bb] * p[k] % mod) % mod;}ans = (ans + (f[n][1][1] * ((1ll << (i + j)) % mod) % mod)) % mod;}printf("%lld\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}
B. 工地难题
计数题，仙姑。
C. 星空遗迹
- 我！T3！打！过！啦！
赛时只砸了两个小时，所以思路不很清晰，分讨漏了好多。
一眼线段树（羁绊 Wis'adel 的力量。首先将每个区间可能所处的状态列举出来：从最左赢到最右，从最右赢到最左，总中间一点赢到两边，整个区间是一种手势。注意到没有两边赢向中间的情况，是因为任意手势如果被两边手势赢，那么可以将它消去，所以两边赢向中间消去无用手势后就成了状态一、二或四。
考虑如何使两个任意状态的区间合并成这四种中的一种，发现中间相邻的两个手势的结果有影响，所以存下。之后根据不同的状态简单分讨合并即可。感谢 int_R 在之前那个超级线段树教会了我如何 pushup 和查询合并一起写，减少了我一半的码量。
其实分讨部分我好像写重了好多，不过无伤大雅。
分讨情况大概是 \(4\times 3\times 4 = 48\) 种，全列出来有点啰嗦，其实简单手模就能出来，你们想看评论下，我再补。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5, x = 1e9;
const int mod = 1e9 + 7;
int n, m;
string s;
int a[N];
struct rmm
{int llx, rlx, wlx;int ln, rn;bool wudi;rmm(){llx = rlx = wlx = ln = rn = 0; wudi = 0;}
} t[N << 2];
namespace Wisadel
{int W(char c){if(c == 'R') return 1;else if(c == 'S') return 2;else return 3;}char M(int x){if(x == 1) return 'R';else if(x == 2) return 'S';else return 'P';}int Wpk(int aa, int bb){if(!aa || !bb) return aa + bb;if(aa == bb) return aa;if(((aa == 1 || aa == 2) && bb == aa + 1) || (aa == 3 && bb == 1) ) return aa;return bb;}#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)rmm Wpushup(rmm a, rmm b){rmm c;c.llx = a.llx, c.rlx = b.rlx;c.ln = c.rn = 0;c.wudi = 0;int wn = Wpk(a.rlx, b.llx);if(a.wudi && b.wudi){if(a.rlx != b.llx){if(wn == a.rlx)//{if(a.ln + 1 > b.rn){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + 1 - b.rn + b.ln;}else{c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn - 1 - a.ln + a.rn;}}else{if(a.ln > b.rn + 1){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln - 1 - b.rn + b.ln;}else{c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn + 1 - a.ln + a.rn;}}}else{if(a.ln > b.rn){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln - b.rn + b.ln;}else{c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn - a.ln + a.rn;}}c.wudi = 1;return c;}if(a.wudi){if(a.rlx != b.llx){if(wn == a.rlx){if(b.ln){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + b.ln + 1;c.wudi = 1;}else if(b.rn){if(a.ln + 1 > b.rn){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + 1 - b.rn;c.wudi = 1;}else{c.wlx = b.wlx;c.rn = b.rn - a.ln - 1 + a.rn;}}else{c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + 1;c.wudi = 1;}}else{if(b.ln){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + b.ln - 1;c.wudi = 1;}else if(b.rn){if(a.ln - 1 > b.rn){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln - 1 - b.rn;c.wudi = 1;}else{c.wlx = b.wlx;c.rn = b.rn - a.ln + 1 + a.rn;}}else{c.wlx = a.wlx;c.rn = a.rn;if(a.ln > 1){c.ln = a.ln - 1;c.wudi = 1;}}}}else{if(b.ln){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln + b.ln;c.wudi = 1;}else if(b.rn){if(a.ln > b.rn){c.wlx = a.wlx;c.rn = a.rn, c.ln = a.ln - b.rn;c.wudi = 1;}else{c.wlx = b.wlx;c.rn = b.rn - a.ln + a.rn;}}else{c.wlx = a.wlx;c.ln = a.ln, c.rn = a.rn;c.wudi = 1;}}return c;}if(b.wudi){if(a.rlx != b.llx){if(wn == b.llx){if(a.rn){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn + 1 + a.rn;c.wudi = 1;}else if(a.ln){if(b.rn + 1 > a.ln){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn + 1 - a.ln;c.wudi = 1;}else{c.wlx = a.wlx;c.ln = a.ln - 1 - b.rn + b.ln;}}else{c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn + 1;c.wudi = 1;}}else{if(a.rn){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn - 1 + a.rn;c.wudi = 1;}else if(a.ln){if(b.rn - 1 > a.ln){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn - 1 - a.ln;c.wudi = 1;}else{c.wlx = a.wlx;c.ln = a.ln + 1 - b.rn + b.ln;}}else{c.wlx = b.wlx;c.ln = b.ln;if(b.rn > 1){c.rn = b.rn - 1;c.wudi = 1;}}}}else{if(a.rn){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn + a.rn;c.wudi = 1;}else if(a.ln){if(b.rn > a.ln){c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn - a.ln;c.wudi = 1;}else{c.wlx = a.wlx;c.ln = a.ln - b.rn + b.ln;}}else{c.wlx = b.wlx;c.ln = b.ln, c.rn = b.rn;c.wudi = 1;}}return c;}//if(a.rlx != b.llx){if(wn == a.rlx)// {if((a.ln && b.ln) || (!a.ln && !a.rn && b.ln) || (a.ln && !b.ln && !b.rn)){c.wlx = a.wlx;c.ln = a.ln + b.ln + 1;}else if(a.ln && b.rn){if(a.ln > b.rn - 1){c.wlx = a.wlx;c.ln = a.ln - b.rn + 1;}else{c.wlx = b.wlx;c.rn = b.rn - 1 - a.ln;}}else if((a.rn && b.ln) || (a.rn && !b.ln && !b.rn)){c.wlx = a.wlx;c.ln = b.ln + 1;c.rn = a.rn;c.wudi = 1;}else if(a.rn && b.rn){c.wlx = b.wlx;c.rn = a.rn + b.rn - 1;}else if(!a.ln && !a.rn && !b.ln && !b.rn){c.wlx = a.wlx;c.ln = 1;}else if(!a.ln && !a.rn && b.rn){c.wlx = b.wlx;c.rn = b.rn - 1;}}if(wn == b.llx)// ←{// cout<<"BUOK!"<<endl;if((a.rn && b.rn) || (!a.ln && !a.rn && b.rn) || (a.rn && !b.ln && !b.rn)){c.wlx = b.wlx;c.rn = a.rn + b.rn + 1;}else if(a.ln && b.rn){if(b.rn > a.ln - 1){c.wlx = b.wlx;c.rn = b.rn - a.ln + 1;}else{c.wlx = a.wlx;c.ln = a.ln - 1 - b.rn;}}else if((a.rn && b.ln) || (b.ln && !a.ln && !a.rn)){c.wlx = b.wlx;c.ln = b.ln;c.rn = a.rn + 1;c.wudi = 1;}else if(a.ln && b.ln){c.wlx = a.wlx;c.ln = a.ln + b.ln - 1;}else if(!a.ln && !a.rn && !b.ln && !b.rn){c.wlx = b.wlx;c.rn = 1;}else if(a.ln && !b.ln && !b.rn){// cout<<"BUOK!"<<endl;c.wlx = a.wlx;c.ln = a.ln - 1;}}}else{if((a.ln && b.ln) || (!a.ln && !a.rn && b.ln) || (a.ln && !b.ln && !b.rn)){c.wlx = a.wlx;c.ln = a.ln + b.ln;}else if((a.ln && b.rn)){if(a.ln > b.rn){c.wlx = a.wlx;c.ln = a.ln - b.rn;}else{c.wlx = b.wlx;c.rn = b.rn - a.ln;}}else if(a.rn && b.ln){c.wlx = a.wlx;c.rn = a.rn, c.ln = b.ln;c.wudi = 1;}else if((a.rn && b.rn) || (!a.ln && !a.rn && b.rn) || (a.rn && !b.ln && !b.rn)){c.wlx = b.wlx;c.rn = a.rn + b.rn;}else if(!a.ln && !a.rn && !b.ln && !b.rn){c.wlx = a.wlx;}}return c;}void Wbuild(int rt, int l, int r){if(l == r){t[rt].llx = t[rt].rlx = t[rt].wlx = a[l];t[rt].ln = t[rt].rn = 0;return;}Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);t[rt] = Wpushup(t[ls], t[rs]);// cout<<l<<' '<<r<<' '<<t[rt].ln<<' '<<t[rt].rn<<' '<<t[rt].wlx<<' '<<t[rt].wudi<<endl;}void Wupd(int rt, int l, int r, int x, int k){if(l == r){t[rt].llx = t[rt].rlx = t[rt].wlx = k;t[rt].ln = t[rt].rn = 0;return;}if(x <= mid) Wupd(ls, l, mid, x, k);else Wupd(rs, mid + 1, r, x, k);t[rt] = Wpushup(t[ls], t[rs]);}rmm Wq(int rt, int l, int r, int x, int y){if(x <= l && r <= y) return t[rt];rmm lans, rans; int ly = 0, ry = 0;if(x <= mid) lans = Wq(ls, l, mid, x, y), ly = 1;if(y > mid) rans = Wq(rs, mid + 1, r, x, y), ry = 1;if(ly && ry){// cout<<l<<' '<<mid<<' '<<r<<endl;// cout<<lans.ln<<' '<<lans.rn<<' '<<lans.wlx<<' '<<lans.wudi<<endl;// cout<<rans.ln<<' '<<rans.rn<<' '<<rans.wlx<<' '<<rans.wudi<<endl;// cout<<endl;return Wpushup(lans, rans);}else if(ly) return lans;else return rans;}short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);freopen("a.in", "r", stdin) , freopen("a.out", "w", stdout);n = qr, m = qr;cin>>s;fo(i, 0, n - 1) a[i + 1] = W(s[i]);Wbuild(1, 1, n);fo(i, 1, m){int op = qr, l = qr, r; char ch;if(op == 1){scanf(" %c", &ch);Wupd(1, 1, n, l, W(ch));}else{r = qr;// fo(j, l, r)// {// cout<<M(Wq(1, 1, n, j, j).wlx);// }// cout<<endl;rmm zc = Wq(1, 1, n, l, r);// cout<<zc.ln<<' '<<zc.rn<<' '<<zc.llx<<' '<<zc.rlx<<' ';printf("%c\n", M(zc.wlx));}}return Ratio;}
}
int main(){return Wisadel::main();}D. 纽带
还没看题。。
末
一开题就感到满满压迫感，三道 \(1e9+7\) 一道不很简单的数据结构。
看到期望和计数直接就似了，不过还是被 T1 控了 1h，有点亏感觉，T3 只打了 2h 多，应该多留出来硬拼的。
以后模拟赛也注意吧，遇到一眼不会的题就暴力略过，后面时间余出来了再尝试正解，不然遇到 T3 这种只是时间不够就太伤了。
不过好在最后改出来了，赢！
完结撒花~
放个原神
