T1 出了个大阴间题（repair）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lb(x) ((x) & (-x))
constexpr int N = (1 << 19) + 1, M = 1e9 + 7;
int n, k, a[20], f[N], g[N][2], h[N][2], sb, sk;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>k; for(int i=1; i<=n; ++i) cin>>f[(1<<(i-1))], g[1<<(i-1)][0] = 1;
for(int i=1; i<=n-2; ++i) sk = (ll)((sk << 1) + 1) % M, sb = ((ll)sb + (ll)sk) % M;
int mx = 1 << n;
for(int i=1; i^mx; ++i) f[i] = max({f[i], f[lb(i)], f[i^lb(i)]});
for(int i=1; i^mx; ++i) for(int j=i; j; j-=lb(j)){
int s = i ^ lb(j);
for(int z=0; z^2; ++z){
int val = f[s] + z, nval = 0;
if(val == f[lb(j)]) nval = val + 1;
else nval = max(val, f[lb(j)]);
int opt = nval != f[i];
g[i][opt] = ((ll)g[i][opt] + (ll)g[s][z]) % M;
h[i][opt] = ((ll)h[i][opt] + (ll)h[s][z] + (ll)g[s][z] * nval % M * k % M) % M;
}
} int opt = g[mx-1][1] != 0;
cout<<(f[mx-1] + opt)<<' '<<(((ll)g[mx-1][opt] * sb % M + (ll)h[mx-1][opt]) % M);
return 0;
}
T2 最简单辣快来做（satellite）
#include<bits/stdc++.h>
using namespace std;
constexpr int B = 1 << 25;
char buf[B], *p1 = buf, *p2 = buf;
#define gt() (p1==p2 && (p2=(p1=buf)+fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++)
template <typename T> inline void rd(T &x){
x = 0; int f = 0; char ch = gt();
for(; !isdigit(ch); ch = gt()) f ^= ch == '-';
for(; isdigit(ch); ch = gt()) x = (x<<1) + (x<<3) + (ch^48);
x = f ? -x : x;
}
char obuf[B], *O = obuf;
#define pt(ch) (O-obuf==B && (fwrite(obuf, 1, B, stdout), O=obuf), *O++ = (ch))
template <typename T> inline void wt(T x){
if(x < 0) pt('-'), x = -x;
if(x >= 10) wt(x / 10); pt(x % 10 ^ 48);
}
#define fw fwrite(obuf, 1, O - obuf, stdout)
#define ll long long
constexpr int MX = 32000, N = 2005;
int n, q, w, H, M, a, b, apw[MX], aspw[MX], bpw[MX], bspw[MX], len;
int h[N], x[N], y[N], px[N], py[N], node[4][N][N];
inline int apow(int k){ return k >= 0 ? (ll)aspw[k/len] * apw[k%len] % M : 1; }
inline int bpow(int k){ return k >= 0 ? (ll)bspw[k/len] * bpw[k%len] % M : 1; }
int main(){
// freopen("satellite2.in", "r", stdin);
// freopen("out.out", "w", stdout);
rd(n), rd(q), rd(w), rd(H), rd(M), rd(a), rd(b);
len = sqrt(max(w, H)) + 1;
apw[0] = 1; for(int i=1; i<=len; ++i) apw[i] = (ll)apw[i-1] * a % M;
aspw[0] = 1; for(int i=1; i<=len; ++i) aspw[i] = (ll)aspw[i-1] * apw[len] % M;
bpw[0] = 1; for(int i=1; i<=len; ++i) bpw[i] = (ll)bpw[i-1] * b % M;
bspw[0] = 1; for(int i=1; i<=len; ++i) bspw[i] = (ll)bspw[i-1] * bpw[len] % M;
for(int i=1; i<=n; ++i) rd(h[i]), rd(x[i]), rd(y[i]), px[i] = x[i], py[i] = y[i];
sort(px+1, px+1+n); int lenx = unique(px+1, px+1+n) - px - 1;
for(int i=1; i<=n; ++i) x[i] = lower_bound(px+1, px+1+lenx, x[i]) - px;
sort(py+1, py+1+n); int leny = unique(py+1, py+1+n) - py - 1;
for(int i=1; i<=n; ++i) y[i] = lower_bound(py+1, py+1+leny, y[i]) - py;
for(int i=1; i<=n; ++i) for(int j=0; j<4; ++j) node[j][x[i]][y[i]] = ((ll)h[i] + (ll)node[j][x[i]][y[i]]) % M;
for(int i=1; i<=lenx; ++i){
int pa = apow(px[i] - px[i-1]);
for(int j=1; j<=leny; ++j){
int pb = bpow(py[j] - py[j-1]);
node[0][i][j] = (((ll)node[0][i][j] + (ll)node[0][i-1][j] * pa % M + (ll)node[0][i][j-1] * pb % M - (ll)node[0][i-1][j-1] * pa % M * pb % M) % M + M) % M;
}
for(int j=leny; j>=1; --j){
int pb = bpow(py[j+1] - py[j]);
node[1][i][j] = (((ll)node[1][i][j] + (ll)node[1][i-1][j] * pa % M + (ll)node[1][i][j+1] * pb % M - (ll)node[1][i-1][j+1] * pa % M * pb % M) % M + M) % M;
}
}
for(int i=lenx; i>=1; --i){
int pa = apow(px[i+1] - px[i]);
for(int j=leny; j>=1; --j){
int pb = bpow(py[j+1] - py[j]);
node[2][i][j] = (((ll)node[2][i][j] + (ll)node[2][i+1][j] * pa % M + (ll)node[2][i][j+1] * pb % M - (ll)node[2][i+1][j+1] * pa % M * pb % M) % M + M) % M;
}
for(int j=1; j<=leny; ++j){
int pb = bpow(py[j] - py[j-1]);
node[3][i][j] = (((ll)node[3][i][j] + (ll)node[3][i+1][j] * pa % M + (ll)node[3][i][j-1] * pb % M - (ll)node[3][i+1][j-1] * pa % M * pb % M) % M + M) % M;
}
}
for(int i=1, qx, qy; i<=q; ++i){
rd(qx), rd(qy); int ans = 0;
int lqx = upper_bound(px+1, px+1+lenx, qx) - px - 1;
int lqy = upper_bound(py+1, py+1+leny, qy) - py - 1;
if(lqx && lqy) ans = ((ll)ans + (ll)node[0][lqx][lqy] * apow(qx-px[lqx]) % M * bpow(qy-py[lqy]) % M) % M;
if(lqx && lqy < leny) ans = ((ll)ans + (ll)node[1][lqx][lqy+1] * apow(qx-px[lqx]) % M * bpow(py[lqy+1]-qy) % M) % M;
if(lqx < lenx && lqy < leny) ans = ((ll)ans + (ll)node[2][lqx+1][lqy+1] * apow(px[lqx+1]-qx) % M * bpow(py[lqy+1]-qy) % M) % M;
if(lqx < lenx && lqy) ans = ((ll)ans + (ll)node[3][lqx+1][lqy] * apow(px[lqx+1]-qx) % M * bpow(qy-py[lqy]) % M) % M;
wt(ans), pt('\n');
} return fw, 0;
}
T3 是我的你不要抢
场上脑子一热拉了泡二分，才反应过来二分没单调性。
就hash， hash完了跑暴力，发现一分也拿不到。尝试记忆化此过程，就可以拿到高贵的 \(100pts\)。
当题目中没给 \(n\) 范围的时候应该就已经意识到了，问题出在 \(n\) 这里。\(n\) 变大时字符串长度 \(L\) 就在变小，所以复杂度可以是 \(\mathcal{O}(\sum L)\) 的。
哦对了，这道题会卡 hash。如果你采用 ull 自然溢出的方式，那么大概率会 \(99WA\)。所以为了避免冲突，需要采用双hash，第一个hash 用 ull 自然溢出，第二个 hash 用取模即可。
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define ull unsigned long long
#define ll long long
#define pi pair<int, int>
constexpr int N = 6e5 + 5, M = 998244353;
int n, q, len[N], mx;
vector<ull> h[N]; vector<ll> hs[N];
ull p[N]; ll ps[N];
string s;
gp_hash_table<int, int> mp[N];
gp_hash_table<int, bool> vis[N];
inline ull get(int id, int l, int r){ return h[id][r] - h[id][l] * p[r-l]; }
inline ll gets(int id, int l, int r){ return ((hs[id][r] - hs[id][l] * ps[r-l]) % M + M) % M; }
inline int work(int x, int y){
int r = min(len[x], len[y]), ans = 0;
for(int i=1; i<=r; ++i)
if(get(x, len[x]-i, len[x]) == h[y][i])
if(gets(x, len[x]-i, len[x]) == hs[y][i]) ans = i;
vis[x][y] = 1; mp[x][y] = ans;
return ans;
}
inline void solve(){
for(int i=1; i<=n; ++i){
cin>>s; len[i] = s.size();
mx = max(mx, len[i]);
h[i].push_back(0);
for(int j=1; j<=len[i]; ++j)
h[i].push_back(h[i][j-1] * 131ull + s[j-1]);
hs[i].push_back(0);
for(int j=1; j<=len[i]; ++j)
hs[i].push_back((hs[i][j-1] * 13331 + s[j-1]) % M);
}
p[0] = 1; for(int i=1; i<=mx; ++i) p[i] = p[i-1] * 131ull;
ps[0] = 1; for(int i=1; i<=mx; ++i) ps[i] = ps[i-1] * 13331 % M;
for(int i=1, x, y; i<=q; ++i){
cin>>x>>y;
if(vis[x][y]) cout<<mp[x][y]<<'\n';
else cout<<work(x, y)<<'\n';
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>q; return solve(), 0;
}
T4 显然也是我整的（graph）
不会 咕~
标签：node,15,int,ll,29,len,rd,hash,2027.9 From： https://www.cnblogs.com/xiaolemc/p/18425901