2025 年 1 月杂题
新年快乐。
本来想写个去年的年终总结，但是细想感觉又无从落笔。
这一年经历了很多，收获了很多。有成长，也有遗憾。
还是没有退役，继续向着省队努力吧。
今年就要成年了，希望我能不辜负过去自己的希望吧。
P3715 [BJOI2017] 魔法咒语
题意
- 给定 \(n\) 个字符串 \(s_i\) 和 \(m\) 个字符串 \(t_i\)。
- 求由若干个 \(s_i\) 顺次相连，长度恰好为 \(l\) 且不包含任何恰好等于 \(t_i\) 的子串的字符串数量。
- 有两个子任务： - \(\sum |s_i|,|t_i|\le 100,l\le 100,1\le n,m\le 50\) - \(\sum |s_i|,|t_i|\le 100,|s_i|\le 2,l\le 10^8,1\le n,m\le 50\)
题解
AC 自动机 \(+\) DP。
不难想到建出 \(t\) 的 AC 自动机，设 \(f_{i,j}\) 表示长度为 \(i\) 的字符串恰好在 AC 自动机上走到结点 \(j\) 的方案数，转移在 AC 自动机上走路即可。
sub1 直接暴力，sub2 用矩阵保存相邻两个 \(i\) 的状态，然后预处理转移即可。
sub1 复杂度 \(O(\left(\sum |t_i|\right)+l\sum s_i)\)，sub2 复杂度 \(O(\left(\sum |s_i|\right)\times\left(\sum |t_i|\right)+\log l\times \left(\sum |t_i|\right)^3)\)。
/// details | 参考代码 open: False typeL success
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=105,mod=1e9+7;
int n,m,l;
string s[N],t[N];
struct Trie{
int tr[N][26],fail[N],vis[N],cntn;
void Insert(const string &s){
int len=s.length(),p=0;
forup(i,0,len-1){
int c=s[i]-'a';
if(!tr[p][c]) tr[p][c]=++cntn;
p=tr[p][c];
}
vis[p]=1;
}
vector<int> e[N];
void dfs(int x){
for(auto i:e[x]){
vis[i]|=vis[x];
dfs(i);
}
}
void Build(){
queue<int> q;
forup(i,0,25){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();q.pop();
e[fail[u]].push_back(u);
forup(i,0,25){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}else{
tr[u][i]=tr[fail[u]][i];
}
}
}
dfs(0);
}
int work(int p,const string &s){
forup(i,0,s.size()-1){
int c=s[i]-'a';
p=tr[p][c];
if(vis[p]) return -1;
}
return p;
}
}mt;
namespace sub1{
int dp[N][N];
void solve(){
dp[0][0]=1;
forup(i,1,l){
forup(p,1,n){
if(i<s[p].size()) continue;
int j=i-s[p].size();
forup(st,0,mt.cntn){
if(dp[j][st]==0) continue;
int tmp=mt.work(st,s[p]);
if(~tmp){
(dp[i][tmp]+=dp[j][st])%=mod;
}
}
}
forup(j,0,mt.cntn){
msg("%d ",dp[i][j]);
}
msg("|\n");
}
int ans=0;
forup(i,0,mt.cntn){
(ans+=dp[l][i])%=mod;
}
printf("%d\n",ans);
}
}
namespace sub2{
int t;
struct Matrix{
int c[N*2][N*2];
Matrix(){
mem(c,0);
}
void init(){
forup(i,0,t-1){
c[i][i]=1;
}
}
Matrix operator *(const Matrix &r){
Matrix res;
forup(i,0,t-1){
forup(j,0,t-1){
forup(k,0,t-1){
(res.c[i][j]+=1ll*c[i][k]*r.c[k][j]%mod)%=mod;
}
}
}
return res;
}
}tr;
Matrix ksm(Matrix a,int b){
Matrix c;c.init();
while(b){
if(b&1) c=c*a;
a=a*a;
b>>=1;
}
return c;
}
void solve(){
int nn=mt.cntn+1;
t=nn*2;
forup(i,0,nn-1){
tr.c[i][i+nn]=1;
}
forup(i,1,n){
forup(j,0,nn-1){
int p=mt.work(j,s[i]);
if(~p) ++tr.c[j+(s[i].size()-1)*nn][p];
}
}
Matrix res=ksm(tr,l);
int ans=0;
forup(i,0,nn-1){
(ans+=res.c[0][i])%=mod;
}
printf("%d\n",ans);
}
}
signed main(){
n=read();m=read();l=read();
forup(i,1,n){
cin>>s[i];
}
forup(i,1,m){
cin>>t[i];
mt.Insert(t[i]);
}
mt.Build();
if(l<=100){
sub1::solve();
}else{
sub2::solve();
}
}
///
P7736 [NOI2021] 路径交点
题意
- 有一个 \(k\) 层的图，第 \(i\) 层有 \(n_i\) 个点，每一层只会向下一层连边，\(n_1=n_k\)。
- 假设每一层的点按编号依次排列在一条直线上，不难发现假如把边画在纸上它们之间可能有交，具体来说，对于第 \(p\) 层向 \(p+1\) 层的连边 \(u_1\to v_1,u_2\to v_2\)，有交当且仅当 \(u_1 > u_2\) 且 \(v_1 < v_2\)
- 设 \(S\) 为一个路径集合大小等于 \(n_1\)，满足第一层所有点均为某一条路径的起点，最后一层均为终点，并且点不重复。设 \(f(S)\) 为路径集合 \(S\) 中的交点总数，求 \(f(S)\) 为偶数的方案数减去 \(f(S)\) 为奇数的方案数。
- \(1\le n_1,k\le 100,n_1\le n_i\le 2n_1,n_k=n_1\)，无重边自环。
题解
LGV 引理版题。
不难发现交点数量和 \(n_1\to n_k\) 对应关系中的逆序对数量奇偶性相同。
于是变成 LGV 引理模板了，参考这篇博客。
中间的 \(e(u,v)\) 可以 bfs 预处理，复杂度大概是 \(O(n_1^3k)\)。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e4+5,inf=0x3f3f3f3f,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int k,n[N],pre[N],m[N];
vector<int> e[N];
int f[N],a[105][105];
void bfs(int x){
mem(f,0);
queue<int> q;
q.push(x);
f[x]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto i:e[u]){
if(!f[i]) q.push(i);
(f[i]+=f[u])%=mod;
}
}
forup(i,1,n[k]){
a[x][i]=f[i+pre[k-1]];
}
}
int det(int n){
int val=1;
forup(i,1,n){
int j=i;
while(j<=n&&!a[j][i]) ++j;
if(j>n) return 0;
if(j!=i){
val=mod-val;
forup(k,1,n) swap(a[i][k],a[j][k]);
}
int inv=ksm(a[i][i],mod-2);
val=1ll*val*a[i][i]%mod;
forup(k,i,n) a[i][k]=1ll*a[i][k]*inv%mod;
forup(j,i+1,n){
fordown(k,n,i){
a[j][k]=(a[j][k]+mod-1ll*a[j][i]*a[i][k]%mod)%mod;
}
}
}
return val;
}
void solve(){
k=read();
forup(i,1,k){
n[i]=read();
pre[i]=pre[i-1]+n[i];
}
forup(i,1,k-1){
m[i]=read();
}
forup(i,1,k-1){
forup(j,1,m[i]){
int u=read()+pre[i-1],v=read()+pre[i];
e[u].push_back(v);
}
}
forup(i,1,n[1]){
bfs(i);
}
printf("%d\n",det(n[1]));
forup(i,1,pre[k]){
e[i].clear();
}
}
signed main(){
int t=read();
while(t--){
solve();
}
}
黑暗爆炸-3238 差异
题意
- 给定一个字符串 \(S\)，设 \(T_i\) 表示从点 \(i\) 开始的后缀，求：
$\( \sum_{1\le i < j\le n}|T_i|+|T_j|-2\mathrm{lcp}(T_i,T_j) \)$
- \(1\le |S|\le 5\times 10^5\)，字符集为小写字母集。
题解
不难发现 \(\sum_{1\le i < j\le n}|T_i|+|T_j|\) 是可以直接算的，于是只需要算 \(\sum_{1\le i < j\le n}\mathrm{lcp}(T_i,T_j)\)。
首先我们不喜欢后缀的最长公共前缀，于是将整个字符串 reverse 一下就变成求前缀的最长公共后缀了。
于是建出 SAM，那么 \(\mathrm{lcp}\) 就转化成了 \(\mathrm{lnk}\) 树上的 \(\mathrm{lca}\)。于是我们将每个点挂在自己的所有祖先，然后再从上往下传即可，注意不要算重。复杂度 \(O(n|\Sigma|)\)。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e6+5,inf=0x3f3f3f3f;
i64 n,pos[N];
char str[N];
i64 tr[N][26],lnk[N],len[N],cnt[N],res[N];
i64 lst=0,cntn=0;;
i64 insert(i64 c){
i64 x=++cntn,p=lst;lst=x;
cnt[x]=1;
len[x]=len[p]+1;
while(~p&&!tr[p][c]){
tr[p][c]=x;
p=lnk[p];
}
if(p==-1){
lnk[x]=0;
return x;
}
i64 q=tr[p][c];
if(len[q]==len[p]+1){
lnk[x]=q;
}else{
i64 _q=++cntn;
len[_q]=len[p]+1;
lnk[_q]=lnk[q];lnk[q]=lnk[x]=_q;
forup(i,0,25){
tr[_q][i]=tr[q][i];
}
while(~p&&tr[p][c]==q){
tr[p][c]=_q;
p=lnk[p];
}
}
return x;
}
vector<i64> e[N];
void dfs1(i64 x){
for(auto i:e[x]){
dfs1(i);
cnt[x]+=cnt[i];
}
res[x]=-2*cnt[x]*len[x];
}
void dfs2(i64 x){
for(auto i:e[x]){
res[i]+=res[x]+2*cnt[i]*len[x];
dfs2(i);
}
}
signed main(){
scanf(" %s",str+1);
n=strlen(str+1);
reverse(str+1,str+n+1);
lnk[0]=-1;
forup(i,1,n){
pos[i]=insert(str[i]-'a');
}
forup(i,1,cntn){
e[lnk[i]].push_back(i);
}
dfs1(0);
dfs2(0);
i64 ans=0;
forup(i,1,n){
ans+=res[pos[i]]+i*n+n*(n+1)/2;
}
printf("%lld\n",ans/2);
}
P2490 [SDOI2011] 黑白棋
题意
- 有一张 \(1\times n\) 的棋盘，上面有 \(k\) 个棋子（\(k\) 是偶数），这些棋子是白色/黑色交替排列的，并且第一个是白色（那么显然最后一个是黑色）。
- 有两个人在这张棋盘上进行游戏，其中先手操作白棋，后手操作黑棋。每一步可以选择不超过 \(d\) 个自己操作的棋子移动一步。白棋只能向右移动，黑棋只能向左移动，不能操作者负。
- 问有多少种摆放方式是先手必胜的。
- \(1\le d\le k\le n\le 10^4\) 其中 \(2\le k\le 100\)。
题解
不难发现这就是一个经典的 k-Nim 问题，结论是将每一堆石子的数量按二进制表示出来后，进行模 \(k+1\) 的不进位加法，若为 \(0\) 则后手必胜，否则先手必胜。
这道题的限制就是总石子个数不能超过 \(n-k\)。
这种因为每一位是独立的，所以考虑按位 DP。具体来说，设 \(f_{i,j}\) 表示考虑低 \(i\) 位，用了 \(j\) 个石子的方案数，转移就枚举这一位应该有 \(d+1\) 的倍数个 \(1\)，用组合数分发到 \(\frac{k}{2}\) 堆石子其中若干个就行了。
然后统计答案还需要计算没用到的格子的位置，也是组合数即可。
复杂度 \(O(n\log n+n^2)\)，这个 \(n^2\) 不会乘 \(\log\) 是因为枚举 \(d+1\) 的倍数这一部分不会超过 \(\frac{n}{2^i}\)，常数很小还是很能通过的。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=20005,M=55,mod=1e9+7;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,k,d;
int dp[25][N];
int fact[N],finv[N];
int binom(int n,int m){
if(n<m) return 0;
return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
signed main(){
n=read();k=read();d=read()+1;
fact[0]=1;
forup(i,1,n) fact[i]=1ll*fact[i-1]*i%mod;
finv[n]=ksm(fact[n],mod-2);
fordown(i,n-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
n-=k;
k>>=1;
dp[0][0]=1;
int mx=0;
for(int i=0,p=1;p<=n;++i,p<<=1){
mx=i+1;
forup(j,0,n){
if(!dp[i][j]) continue;
forup(t,0,min(k,(n-j)/(d*p))){
(dp[i+1][j+d*p*t]+=1ll*dp[i][j]*binom(k,d*t)%mod)%=mod;
}
}
}
int ans=0;
forup(i,0,n){
(ans+=1ll*dp[mx][i]*binom(n-i+k,k)%mod)%=mod;
}
ans=(binom(n+k*2,k*2)+mod-ans)%mod;
printf("%d\n",ans);
}
P5417 [CTSC2016] 萨菲克斯·阿瑞
题意
- 问满足以下所有条件的字符串 \(s\) 可能有多少种不同的后缀数组： - 长度为 \(n\)，字符集大小为 \(m\)。 - 第 \(i\) 种（从小往大排列）字符出现次数不超过 \(c_i\)。
- \(1\le n,m\le 200,0\le c_i\le n,\sum c_i\ge n\)
题解
很厉害的一道题。
首先后缀数组显然不能直接做，考虑经典转化：将后缀数组转化为字符的大小关系。
具体来说，设后缀数组为 \(sa\)（\(sa_i\) 表示字典序第 \(i\) 小的后缀），逆排列为 \(rk\)，那么 \(s_{sa_i}\le s_{sa_{i+1}}\)，并且若 \(rk_{sa_i+1} > rk_{sa_{i+1}+1}\) 则这个 \(\le\) 必须替换为 \( < \)。即一个后缀数组能映射到一个由 \( < \) 或 \(\le\) 连接的大小关系序列。
但是这个关系序列显然无法映射到后缀数组。一个观察是若钦定不同字符的数量恰好等于 \( < \) 的个数加一，那么这个关系序列就能映射到唯一的字符串，进而映射到唯一的后缀数组。而不难发现我们只要确定由 \(<\) 连接的每一段长度（不妨设为 \(a_i\)）后，不同的后缀数组数量就是 \(\frac{(\sum a_i)!}{\prod a_i!}\)，但是显然会算重，这启发我们进行容斥。
具体来说，我们对关系序列进行计数，每两个 \(<\) 之间的 \(s_{sa_i}\) 尽量用同种字符填满，然后钦定 \(k\) 个 \(<\) 替换为 \(\le\)，并且容斥系数为 \((-1)^k\)。
不难想到设 \(f_{i,j,k}\) 表示考虑前 \(i\) 种字符，已经填了前 \(j\) 位，并且上一段的末尾为 \(k\) 的方案数，因为方案数带 \(n!\) 的系数，根据套路把它拆出来，那么转移有三种：
- \(f_{i,j,k}\gets f_{i-1,j-c_i,k}\)：将 \(c_i\) 个字符全部填进这一段，并且不新建下一段。
- \(f_{i,j,k}\gets -\sum_{t=1}^{c_i}f_{i-1,j-t,k}\)：填 \(t\) 个字符进这一段，但是钦定这个 \(<\) 变成 \(\le\)，即不新建一段，那么有 \(-1\) 的系数。
- \(f_{i,j,j}\gets \frac{1}{(j-k)!}\sum_{t=1}^{c_i}f_{i-1,j-t,k}\)：填 \(t\) 个字符进这一段，并且新建一段。
为什么后面两种转移从 \(1\) 开始枚举 \(t\) 呢？虽然实际选的字符并不一定是一个前缀，但是由于我们只关注每一段的长度所以并不会算漏情况。反而如果从 \(0\) 开始枚举就可能需要加一堆特判。
复杂度 \(O(n^2m)\)，需要前缀和优化。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=505,mod=1e9+7;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,c[N];
int f[2][N][N],sum[N][N];
int fact[N],finv[N];
signed main(){
n=read();m=read();
forup(i,1,m){
c[i]=read();
}
int cntn=0;
forup(i,1,m) if(c[i]) c[++cntn]=c[i];
m=cntn;
fact[0]=1;
forup(i,1,n) fact[i]=1ll*fact[i-1]*i%mod;
finv[n]=ksm(fact[n],mod-2);
fordown(i,n-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
f[0][0][0]=1;
forup(i,0,n){
sum[i][0]=1;
}
int ans=0;
forup(i,1,m){
int p=i&1,q=p^1;
mem(f[p],0);
forup(j,0,n){
forup(k,0,j){
if(j>=c[i]+k) (f[p][j][k]+=f[q][j-c[i]][k])%=mod;
int vv;
if(j>c[i]){
vv=(sum[j-1][k]+mod-sum[j-c[i]-1][k])%mod;
}else{
vv=sum[j-1][k];
}
f[p][j][k]=(f[p][j][k]+mod-vv)%mod;
(f[p][j][j]+=1ll*vv*finv[j-k]%mod)%=mod;
}
}
(ans+=f[p][n][n])%=mod;
mem(sum,0);
forup(j,0,n){
forup(k,0,j){
sum[j][k]=f[p][j][k];
if(j) (sum[j][k]+=sum[j-1][k])%=mod;
}
}
}
printf("%lld\n",1ll*ans*fact[n]%mod);
}
CF1746F Kazaee
题意
- 有一个长度为 \(n\) 的序列 \(a\)，维护两个操作共 \(m\) 次： - 单点修改。 - 区间查询是否每个数出现次数都是 \(k\) 的倍数，每次询问的 \(k\) 不一定相同。
- \(1\le n,q\le 3\times 10^5,1\le a_i\le 10^9\)。
题解
典题，但是 zky 提供了一个拓展性更强的做法。
一个想法是给每个值映射一个随机权值，查询区间和是否为 \(k\) 的倍数。多映射几组错误概率就很低了。
但是我们发现随机权值的范围缩小到 \(0\) 或者 \(1\) 仍然可以，此时出错当且仅当若干个不为 \(k\) 倍数的数区间总个数是 \(k\) 的倍数，然后全选或者全不选，发现只要存在这样的错误方案就必定会存在若干个正确方案（修改出错部分的一个子集），那么错误概率不超过 \(\frac{1}{2}\)（恰好两个数加起来出错，错误比例为 \(\frac{2}{4}\)），于是随机 \(40\) 组映射差不多就能对了，错误概率 \(2^{-40}\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f;
int n,q,a[N];
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt[41];
map<int,vector<int> > mp;
mt19937 mr(20071221);
int Rd(int l,int r){return (unsigned int)mr()%(r-l+1)+l;}
signed main(){
n=read();q=read();
forup(i,1,n){
a[i]=read();
if(!mp.count(a[i])){
vector<int> vec;
forup(i,0,40){
vec.push_back(Rd(0,1));
}
mp[a[i]]=vec;
}
vector<int> p=mp[a[i]];
forup(j,0,40){
mt[j].upd(i,p[j]);
}
}
forup(i,1,q){
int op=read();
if(op==1){
int x=read(),v=read();
vector<int> p=mp[a[x]];
forup(j,0,40){
mt[j].upd(x,-p[j]);
}
a[x]=v;
if(!mp.count(a[x])){
vector<int> vec;
forup(i,0,40){
vec.push_back(Rd(0,1));
}
mp[a[x]]=vec;
}
p=mp[a[x]];
forup(j,0,40){
mt[j].upd(x,p[j]);
}
}else{
int l=read(),r=read(),k=read();
bool flag=true;
forup(j,0,40){
if((mt[j].sum(r)-mt[j].sum(l-1))%k!=0){
flag=false;
break;
}
}
puts(flag?"YES":"NO");
}
}
}
P1224 [NOI2013] 向量内积
题意
- 给定 \(n\) 个 \(d\) 维向量，求是否存在两个向量 \(v_i,v_j(i\ne j)\) 点积为 \(k\) 的倍数，输出这两个向量的下标。
- 两个 subtask： - \(1\le n\le 10^4,1\le d\le 100,2\le k\le 3\)。 - \(1\le n\le 10^5,1\le d\le 30,2\le k\le 3\)。
题解
zky 的神秘随机化做法。
首先不妨直接在模意义下进行计算。
考虑 \(k=2\)，那么点积只有可能是 \(0\) 或者 \(1\)。显然不存在这样的一对 \((i,j)\) 当且仅当对于任意 \(i,j\) 有 \(v_i\cdot v_j = 1\)。注意到点积对于向量加法有分配律，那么我们随机取出一个向量的集合 \(S\)，将其线性加起来得到 \(V\)。然后用所有不在 \(S\) 中的向量和 \(V\) 相乘，显然某 \(i\in S\) 和 \(j\notin S\) 满足 \(v_i\cdot v_j=0\) 仅当 \(j\) 和 \(V\) 的点积奇偶性和 \(|S|\) 的奇偶性不同。
考虑这个判定条件的正确率，首先不难发现判定错误当且仅当有偶数对 \((i,j)\) 被分开了，发现无论有几对这样的数对，偶数对的情况都不会多于奇数对的情况，即正确率不低于 \(\frac{1}{2}\)。那么进行 \(T\) 次错误概率就是 \(2^{-T}\)，复杂度 \(O(\frac{Tnd}{\omega})\)。
然后考虑 \(k=3\)，发现在模 \(3\) 意义下非 \(0\) 数的平方都是 \(1\)，那么取点积的平方，则 \(\left(\sum_{p=1}^dv_{i,p}v_{j,p}\right)=\sum_{1\le x,y\le d}v_{i,x}v_{i,y}v_{j,x}v_{j,y}\)，于是转化为长度为 \(d^2\) 的向量点积就又可以用奇偶性判断了。这个复杂度是 \(O(\frac{Tnd^2}{\omega})\)，错误概率还是 \(2^{-T}\)。
因为要可变长度 bitset，代码里用了模板技巧。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using uchar=unsigned char;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,M=105,inf=0x3f3f3f3f;
const int T=50;
int n,m,p;
template<int D>
struct Vec{
bitset<D> v[2];
int operator *(const Vec<D> &r){
if(p==2){
return (v[0]&r.v[0]).count()&1;
}else{
return ((v[0]&r.v[0]).count()+(v[1]&r.v[1]).count()
+2*(v[0]&r.v[1]).count()+2*(v[1]&r.v[0]).count())%3;
}
}
Vec operator +(const Vec<D> &r){
Vec res;
if(p==2){
res.v[0]=v[0]^r.v[0];
}else{
bitset<D> v0,rv0;v0.set();rv0.set();
v0=v0^v[0]^v[1];
rv0=rv0^r.v[0]^r.v[1];
res.v[0]=((v[1]&r.v[1])|(v0&r.v[0])|(v[0]&rv0));
res.v[1]=((v[0]&r.v[0])|(v0&r.v[1])|(v[1]&rv0));
}
return res;
}
};
vector<vector<uchar>> s;
mt19937 mr(20071221);
int Rd(int l,int r){return (unsigned int)mr()%(r-l+1)+l;}
bool vis[N];
template<int M=1>
void work(int n,int m){
if(M<=m) work<min(M*2,10001)>(n,m);
vector<Vec<M>> a(n+1);
forup(i,1,n){
forup(j,1,m){
if(s[i][j]!=0){
a[i].v[s[i][j]-1].set(j,1);
}
}
}
forup(i,1,T){
Vec<M> vec;
int cnt=0;
forup(j,1,n){
vis[j]=Rd(0,1);
if(vis[j]){
cnt=(cnt+1)%p;
vec=vec+a[j];
}
}
forup(i,1,n){
forup(j,i+1,n){
msg("%d ",a[i]*a[j]);
}
msg("|\n");
}
forup(i,1,n){
msg("%d ",vis[i]);
}msg("|\n");
forup(j,1,n){
if(!vis[j]){
int sum=0;
forup(k,1,n){
if(vis[k]){
(sum+=a[j]*a[k])%=p;
}
}
if(a[j]*vec!=cnt){
msg("(%d)\n",j);
forup(k,1,n){
if(!vis[k]) continue;
if(a[j]*a[k]==0){
if(j>k) swap(j,k);
printf("%d %d\n",j,k);
exit(0);
}
}
assert(0);
}
}
}
}
};
void solve3(){
vector<vector<uchar>> b;
b.resize(n+1,vector<uchar>(m*m+1,0));
forup(i,1,n){
forup(j,1,m){
forup(k,1,m){
b[i][(j-1)*m+k]=s[i][j]*s[i][k]%p;
}
}
}
s=b;
work(n,m*m);
};
signed main(){
n=read();m=read();p=read();
s.resize(n+1,vector<uchar>(m+1));
forup(i,1,n){
forup(j,1,m){
s[i][j]=read()%p;
}
}
if(p==2){
work(n,m);
}else{
solve3();
}
puts("-1 -1");
}
zky 原创题
暂时无法提交。
题意
- 给定一个长度为 \(n\) 的整数序列 \(a\)，支持以下两种操作共 \(m\) 次： - 区间翻转。 - 查询从区间中选出一个子集能获得的最大异或和。
- \(1\le n,q\le 5\times 10^4,0\le a < 2^{60}\)
题解
神秘啊神秘。
考虑这样做：随机一个 \(0/1\) 序列 \(b\)，再维护一个 \(c_i=a_ib_i\)，然后我们将区间 \(c_i\) 的异或和拎出来。
不难发现当我们随机 \(b_i\) 的组数足够多时，把每个 \(c_i\) 的区间异或和当成一个向量得到的张成空间（下称“新空间”）显然是区间张成空间（下称“原空间”）的子空间，并且很有可能就是原空间的张成空间。
那么具体多有可能呢。首先不妨把原空间看作一个 \([0,2^l)\) 的集合，那么若新空间是原空间的真子空间，则新空间的正交补空间维数必定不小于 \(1\)，即存在一个向量 \(v\) 和新空间内所有向量全部垂直。显然对于一个向量，在全集中恰有 \(\frac{1}{2}\) 的向量和它垂直，那么存在一个向量和这些东西全部垂直的概率就是 \(2^{-T}\)（其中 \(T\) 是取的组数）。
那么平衡树维护 \(T\) 个区间异或和即可，复杂度 \(O(nT+qT(\log n+\log V))\)。据 zky 说 \(T\) 取 \(100\) 是不难过的。
代码懒得写了。
一般图最大匹配
题意
- 给定一张无向图，求最大匹配（找到最大的边集使得任意一个点至多出现一次）。
- \(1\le n\le 500\)
题解
这道题正解 \(n\le 1000\) 是带花树算法（我不会），但是 zky 讲了一个很精妙的线性代数做法。
考虑设计矩阵 \(G\)：
对于 \(i\le j\)，若 \(i,j\) 之间有边，则 \(G_{i,j}=x_{i,j},G_{j,i}=-x_{i,j}\)（这里的 \(x_{i,j}\) 是一个代数对象，对于不同的 \((i,j)\) 两两不同）。
结论：\(\det G\ne 0\) 等价于原图存在完美匹配。
为什么呢？考虑行列式的定义，\(\sum_p\pi(p)G_{i,p_i}\)（这里 \(\pi\) 表示若 \(p\) 逆序对数量为奇数则为 \(-1\)，否则为 \(+1\)），不难发现 \(i\to p_i\) 构成了一个置换环，注意到若存在环为奇数则必定能反过来走一遍抵消，所以计算到 \(\det\) 里面的都是环长全为偶数的方案了。显然环长全为偶数有平凡解。
那么怎么求最大匹配呢？我们猜测答案是 \(\frac{\mathrm{rank}\;G}{2}\)。
首先不难发现取出最大匹配对应的行，这些行线性无关（否则行列式就是 \(0\) 了），则矩阵的值大于等于二倍最大匹配。
并且我们显然可以取出一个 \(\mathrm{rank}\;G\times \mathrm{rank}\;G\) 的矩阵行列式不等于 \(0\)，于是二倍最大匹配大于等于矩阵的秩。
显然我们不能直接算多项式，于是我们随机 \(x\) 求出 \(\mathrm{rank}\) 即可，复杂度 \(O(n^3)\)。
代码就不贴了。
LOJ#178 多项式求根
题意
- 给定一个多项式方程 \(f(x)=\sum_{i=0}^na_ix^i=0\)，求在模质数 \(p\) 意义下的所有根。
- \(1\le n\le 100,3\le p\le 10^9\)
题解
很妙的一个东西。
首先要求根的话我们肯定希望写成 \(\prod(x-b_i)\) 的形式。
不难发现 \(\prod_{i=0}^{p-1}(x-i)=x^p-x\)，因为带任何值进去都是 \(0\)。那么我们求出 \(\gcd(f,x^p-x)\) 就能得到一个只有根的东西了。并且我们又找到了一个分理出一部分根的方法。
具体来说，我们构造一个多项式 \(g\) 包含 \([0,p-1]\) 中的一部分根，取 \(h=\gcd(f,g)\) 即可把 \(f\) 的根分为 \(h\) 中的和 \(\frac{f}{h}\) 中的两部分了，一直递归到只有一个根就对了。
那么如何构造多项式 \(g\) 呢？注意到在模 \(p\) 意义下，任何数的 \(\frac{p-1}{2}\) 不是 \(1\) 就是 \(-1\)（取决于这个数是不是二次剩余），而根据经典结论，二次剩余大约占 \(\frac{1}{2}\)，那么我们取 \(g=h^{\frac{p-1}{2}}-1\) 即可（此处 \(h\) 是一个随机的多项式）。
但是我不会写多项式全家桶，所以留坑待补。
P5811 [IOI2019] 景点划分
题意
- 给定一张 \(n\) 个点 \(m\) 条边的无向图，将其划分为大小分别为 \(a,b,c(a+b+c=n)\) 的三个点集，使得其中至少两个点集是连通的。构造方案或者判断无解。
- \(3\le n\le 10^5,2\le m\le 2\times 10^5\)，无重边自环，图连通。
题解
貌似有很巧妙的做法，但是可以直接利用双极定向知识比较板地做。
首先不妨设 \(a\le b\le c\)，显然集合 \(A,B\) 更容易是连通的，下文称 \(A\) 中为红点，\(B\) 中为蓝点。
注意到任意一个点双都能双极定向，那么我们先建立原图的广义圆方树（下文简称圆方树），考虑寻找一个点双同时包含红蓝两色的点。不难想到点双有且仅有一个，首先必定存在至少一个解包含一个这样的点双，并且如果有两个同时包含红蓝两色的点双，那么中间那个割点不管取什么颜色都不对了。
那么我们枚举每一个方点，找到它最大的子树大小（只算子树内圆点）记为 \(sz\)。
- 若 \(sz > n-a\)，那么显然这个方点不可能有解。
- 否则，若 \(sz\ge b\)，那么必定能在这个子树内找到一个大小 \(\ge b\) 的连通块同时，在子树外找到大小 \(\ge a\) 的，直接构造即可。
- 否则，我们对这个点双进行双极定向（随便找 \(s\ne t\) 即可），由于每个子树大小都 \(< b\)，那么前缀和不可能从小于 \(a\) 突变到大于等于 \(a+b\)。由于 \(a\le b\le c\)，那么在第一个前缀大于等于 \(a\) 的位置，后面的后缀必定大于等于 \(c\) 于是也大于等于 \(b\)，那么就能构造出来的。
显然代码不好写，现在正好已经很晚了于是留坑待补。
CF1073G Yet Another LCP Problem
题意
- 给定一个长度为 \(n\) 的字符串，有 \(m\) 次询问。
- 每次询问给定两个下标的集合 \(A,B\)，求出 \(\sum_{i\in A}\sum_{j\in B}\mathrm{lcp}(i,j)\)。
- 此处 \(\mathrm{lcp}(i,j)\) 表示后缀 \([i,n]\) 和后缀 \([j,n]\) 的最长公共前缀。
- \(1\le n\le 2\times 10^5\)
题解
一个完全不动脑子的 SAM 做法。
首先把字符串 std::reverse 一下，不难想到两两在 parent tree 上求 \(\mathrm{lca}\)。
然后发现可以将每个点点权置为为 \(\mathrm{len_{\mathit{i}}}-\mathrm{len_{link_{\mathit{i}}}}\)（除去根节点权值为 \(0\)），这样 \(\mathrm{lca}\) 就转化为了两条延伸到 \(1\) 的垂直树链交的点权和。
然后直接树剖维护即可，注意链底的等价类不一定被全部包含，可以单独维护。总复杂度 \(O(n\log^2 n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=4e5+5,inf=0x3f3f3f3f;
i64 n,m;
char str[N];
i64 pos[N];
i64 tr[N][26],lnk[N],len[N];
i64 cntn,lst;
vector<i64> e[N];
void Insert(i64 c){
i64 x=++cntn,p=lst;lst=x;
len[x]=len[p]+1;
while((~p)&&!tr[p][c]){
tr[p][c]=x;
p=lnk[p];
}
if(p==-1){
lnk[x]=0;
return;
}
i64 q=tr[p][c];
if(len[q]==len[p]+1){
lnk[x]=q;
}else{
i64 _q=++cntn;
len[_q]=len[p]+1;
lnk[_q]=lnk[q];
lnk[x]=lnk[q]=_q;
forup(i,0,25) tr[_q][i]=tr[q][i];
while((~p)&&tr[p][c]==q){
tr[p][c]=_q;p=lnk[p];
}
}
return;
}
i64 dfn[N],Tm,sz[N],mp[N];
i64 son[N];
void dfs(i64 x){
sz[x]=1;son[x]=0;
for(auto i:e[x]){
dfs(i);
sz[x]+=sz[i];
if(!son[x]||sz[i]>sz[son[x]]) son[x]=i;
}
}
i64 hig[N];
void dfs2(i64 x,i64 hh){
dfn[x]=++Tm;
mp[dfn[x]]=x;
hig[x]=hh;
if(son[x]){
dfs2(son[x],hh);
}
for(auto i:e[x]){
if(i==son[x]) continue;
dfs2(i,i);
}
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 val[N<<2],sum[N<<2],mark[N<<2];
void Build(i64 l=1,i64 r=Tm,i64 id=1){
mark[id]=sum[id]=0;
if(l==r){
if(mp[l]==0){
val[id]=len[mp[l]];
}else{
val[id]=len[mp[l]]-len[lnk[mp[l]]];
}
// msg("%lld(%lld %lld)%lld|\n",id,l,r,val[id]);
return;
}
Build(lson);Build(rson);
val[id]=val[id<<1]+val[id<<1|1];
msg("%lld(%lld %lld)%lld|\n",id,l,r,val[id]);
}
void PushUp(i64 id){
sum[id]=sum[id<<1]+sum[id<<1|1];
}
void modi(i64 id,i64 V){
sum[id]+=V*val[id];
mark[id]+=V;
}
void PushDown(i64 id){
modi(id<<1,mark[id]);
modi(id<<1|1,mark[id]);
mark[id]=0;
}
void Update(i64 L,i64 R,i64 X,i64 l=1,i64 r=Tm,i64 id=1){
if(L<=l&&r<=R){
modi(id,X);
// msg("%lld %lld|%lld %lld|\n",l,r,val[id],sum[id]);
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
i64 Query(i64 L,i64 R,i64 l=1,i64 r=Tm,i64 id=1){
if(L<=l&&r<=R){
return sum[id];
}
i64 res=0;
if(mark[id]) PushDown(id);
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
}mt;
struct BIT{
i64 c[N];
void upd(i64 x,i64 k){for(;x<=Tm;x+=x&-x)c[x]+=k;}
i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}t2;
void Update(i64 x,i64 v){
while(~x){
mt.Update(dfn[hig[x]],dfn[x],v);
x=lnk[hig[x]];
}
}
i64 Query(i64 x){
i64 res=0;
while(~x){
res+=mt.Query(dfn[hig[x]],dfn[x]);
x=lnk[hig[x]];
}
return res;
}
signed main(){
n=read();m=read();
scanf(" %s",str+1);
reverse(str+1,str+n+1);
lnk[0]=-1;
lst=cntn=0;
forup(i,1,n){
Insert(str[i]-'a');
}
i64 p=0;
forup(i,1,n){
p=tr[p][str[i]-'a'];
pos[i]=p;
}
// forup(i,0,cntn){
// forup(j,0,2){
// msg("%lld ",tr[i][j]);
// }
// msg("|%lld %lld|\n",len[i],lnk[i]);
// }
forup(i,1,cntn){
e[lnk[i]].push_back(i);
}
dfs(0);
dfs2(0,0);
forup(i,1,cntn){
msg("%lld ",dfn[i]);
}
msg("|\n");
mt.Build();
forup(i,1,m){
i64 cl=read(),cr=read(),res=0;
vector<i64> vec;
forup(i,1,cl){
i64 p=read();
p=n-p+1;
vec.push_back(p);
Update(lnk[pos[p]],1);
t2.upd(dfn[pos[p]],len[pos[p]]-len[lnk[pos[p]]]);
t2.upd(dfn[pos[p]]+sz[pos[p]],-(len[pos[p]]-len[lnk[pos[p]]]));
}
forup(i,1,cr){
i64 p=read();
p=n-p+1;
res+=Query(pos[p])+t2.sum(dfn[pos[p]]);
}
printf("%lld\n",res);
for(auto p:vec){
Update(lnk[pos[p]],-1);
t2.upd(dfn[pos[p]],-(len[pos[p]]-len[lnk[pos[p]]]));
t2.upd(dfn[pos[p]]+sz[pos[p]],len[pos[p]]-len[lnk[pos[p]]]);
}
}
}