A - XOR和路径
题意：给定一个 \(N\) 点 \(M\) 边的无向连通图，边有非负权值 \(w\)。从 \(1\) 号点出发，每一步等概率随机选择当前点的一条出边（包括自环）并移动到相邻点，直到到达 \(N\) 号点停止。求路径上所有边权的异或和的期望值，保留三位小数。\(N \le 100\)，\(M \le 10000\)，\(0 \le w \le 10^9\)，可能有重边和自环。
可以对于每一位去处理，发现可以得出
移项后，可以发现可以用高斯消元求解。
时间复杂度 \(O( n^3\log a)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x[10005],y[10005],val[10005],du[105];
long double ans,G[105][105];
const long double eps=1e-10;
long double solve(int w){for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)G[i][j]=0;for(int i=1;i<n;i++) G[i][i]=du[i];G[n][n]=1;for(int i=1;i<=m;i++){if(!((val[i]>>w)&1)){if(x[i]<n) G[x[i]][y[i]]--;if(x[i]!=y[i]){if(y[i]<n) G[y[i]][x[i]]--;}}else{if(x[i]<n) G[x[i]][y[i]]++,G[x[i]][n+1]++;if(x[i]!=y[i]){if(y[i]<n) G[y[i]][n+1]++,G[y[i]][x[i]]++;}}}for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++)if(fabs(G[j][i])>=fabs(G[i][i]))swap(G[i],G[j]);long double x=G[i][i];for(int j=i;j<=n+1;j++) G[i][j]/=x;for(int j=i+1;j<=n;j++)if(fabs(G[j][i])>eps){long double Bi=G[j][i]/G[i][i];for(int k=i;k<=n+1;k++) G[j][k]-=G[i][k]*Bi;}}for(int i=n;i>=1;i--)for(int j=i+1;j<=n;j++)G[i][n+1]-=G[i][j]*G[j][n+1];return G[1][n+1];
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&x[i],&y[i],&val[i]),du[x[i]]++;if(x[i]!=y[i]) du[y[i]]++;}for(int w=0;w<=30;w++) ans+=solve(w)*(1ll<<w);return printf("%.3Lf\n",ans),0;
}
B - 数字根
题意：给定长度为 \(N\) 的序列 \(A_i\)（\(0 \le A_i < 10^9\)）。定义数字根为反复求各位数字和直到小于 \(10\)。区间 \([l,r]\) 的数字根即 \(\sum_{i=l}^r A_i\) 的数字根。有 \(Q\) 次询问，每次给出区间 \([L,R]\)，求该区间内所有连续子区间的数字根中，最大的前 \(5\) 个不同值（降序），不足 \(5\) 个则用 \(-1\) 补足。\(N,Q \le 10^5\)。
首先对于一个数，计算它的数字根是很快的，由于是取和，所以这个数最大是可以达到 \(10^{15}\)，变完一次，可以表示 \(0\) 到 \(14 \times 9\) 中的每个数，而这些数最多再次变化两次就是最终答案了。
由于最终这个数小于等于 \(9\)，相当于只要我们判断这 \(10\) 个数是否在一段区间内有出现。进一步的，只用我们判断，对于每一个位置，它往前最近多近，就可以找到这样一个数。
后来手玩了一下，发现唐了，这个其实就是 \(x \mod 9\)，特别的，为 \(0\) 时是 \(9\)。
这样就好做了，求一遍前缀和。题目转化为是否能在 \(L\le l \le r\le R\)，使得 \(qz_r-qz_{l-1} \mod 9=k\)。考虑预处理，记录每个点往前最近多少就能找到一个满足 qz 相减为 \(k\)，发现这个可以直接用桶维护（发现 qz 先取模其实没有影响），然后询问的时候相当于就是区间最大值问题，直接线段树。
\(O(9(n+Q) \log n)\)
后来交了，发现 WA 了，90pts，少考虑了 0 的情况，需要特殊判断一下。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,qz[100005],lst[10],q;
struct SegTree{int Max[100005<<2];void change(int rt,int l,int r,int x,int num){Max[rt]=max(Max[rt],num);if(l==r) return;int mid=l+r>>1;if(x<=mid) change(rt<<1,l,mid,x,num);else change(rt<<1|1,mid+1,r,x,num);}int query(int rt,int l,int r,int L,int R){if(l==L&&r==R) return Max[rt];int mid=l+r>>1;if(R<=mid) return query(rt<<1,l,mid,L,R);else if(mid+1<=L) return query(rt<<1|1,mid+1,r,L,R);else return max(query(rt<<1,l,mid,L,mid),query(rt<<1|1,mid+1,r,mid+1,R));}
}tree[10];
int qz0[100005];
signed main(){scanf("%lld",&n);for(int i=1;i<9;i++) lst[i]=-1;for(int i=1,x;i<=n;i++) scanf("%lld",&x),qz[i]=(qz[i-1]+x)%9,qz0[i]=(qz0[i-1]+(x==0));for(int i=1;i<=n;i++){for(int j=0;j<9;j++){int w=(((qz[i]-j+9)%9==0)?9:((qz[i]-j+9)%9));if(qz0[i]-qz0[i-1]==0) tree[w].change(1,1,n,i,lst[j]+1);}lst[qz[i]]=i;}scanf("%lld",&q);for(int T=1,l,r,cnt;T<=q;T++,putchar('\n')){scanf("%lld%lld",&l,&r),cnt=0;for(int ans=9;ans>=1;ans--)if(tree[ans].query(1,1,n,l,r)>=l){printf("%lld ",ans),cnt++;if(cnt==5) break;}bool used=0;for(int i=cnt+1;i<=5;i++){if(qz0[r]-qz0[l-1]&&!used){used=1,printf("0 ");continue;}printf("-1 ");}}return 0;
}
C - 玄武密码
题意：给定一个长度为 \(n\)（\(n \le 10^7\)）的母串 \(s\)，以及 \(m\)（\(m \le 10^5\)）个模式串 \(t_i\)（\(|t_i| \le 100\)），字符集为 {E,S,W,N}。对每个 \(t_i\)，求其最长的前缀长度，使得该前缀是 \(s\) 的子串。
考虑对 \(m\) 个 \(t\) 串构建 AC 自动机，并在构建 trie 时，对每个点记录它被哪个串到过，且它是第几个被到的。然后跑一遍匹配，用 topu 优化。最后遍历每个点及其所记录的信息，更新每个询问的答案。
时间复杂度 \(O(n+m|t|)\)
#include<bits/stdc++.h>
using namespace std;
int n,m,trie[10000005][4],Cnt,fail[10000005],In[10000005],rt,cnt,ans[100005];
bitset<10000005> vis;
vector<pair<int,int> > v[10000005];
string s,x;
#define calc(x) (x=='E'?0:(x=='S'?1:(x=='W'?2:3)))
void insert(string s,int id){rt=0;int cnt=0;for(char c:s){if(!trie[rt][calc(c)]) trie[rt][calc(c)]=++Cnt;rt=trie[rt][calc(c)],cnt++,v[rt].push_back({id,cnt});}
}
queue<int> q;
void getfail(){for(int i=0;i<4;i++)if(trie[0][i])q.push(trie[0][i]),In[0]++;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<4;i++){if(trie[x][i]) fail[trie[x][i]]=trie[fail[x]][i],In[trie[fail[x]][i]]++,q.push(trie[x][i]);else trie[x][i]=trie[fail[x]][i];}}
}
void topu(){for(int i=0;i<=Cnt;i++)if(!In[i])q.push(i);while(!q.empty()){int x=q.front();q.pop();vis[fail[x]]=(vis[fail[x]]|vis[x]),In[fail[x]]--;if(!In[fail[x]]) q.push(fail[x]); }for(int i=0;i<=Cnt;i++)if(vis[i])for(pair<int,int> j:v[i]) ans[j.first]=max(ans[j.first],j.second);
}
signed main(){scanf("%d%d",&n,&m),cin>>s;for(int i=1;i<=m;i++) cin>>x,insert(x,i);getfail(),rt=0;for(int c:s) rt=trie[rt][calc(c)],vis[rt]=1;topu();for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}