轻度的断食似乎对精神状态有好处。不过相比两年前还是吃的多些。两年前今天中午吃的一点东西是我当时一天的量。
T3 我会 60 的部分分，但是没写。问就是正解忘了板子怎么打。
不如直接脖子右拧。
晚上又没吃饭，感觉精神状态好了一些。明天早上得吃了，再不吃按照经验我妈得找我了。但是好饿！！！
字符串
猪脑过载。
一个前缀的出现位置是失配树的子树。于是建正反串的失配树，变成两个树的某个子树求交。把 \(x\) 放到 \((dfn_{x,1},dfn_{x,2})\) 点上，变成二维数点。
Delov 用 DAG 链剖分过了，十分震撼。chino 写了个后缀树树剖，这样好像可以直接跳了，我赛时怎么没写。大概真被 T3 整不会了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,q,nxt[200010];
char s[200010];
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs,sum;
}tree[200010<<5];
int t,rt[200010];
void pushup(int rt){
tree[rt].sum=tree[lson].sum+tree[rson].sum;
}
void update(int &rt,int pre,int L,int R,int pos){
rt=++t;
tree[rt]=tree[pre];
if(L==R){
tree[rt].sum++;return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,tree[pre].ls,L,mid,pos);
else update(rson,tree[pre].rs,mid+1,R,pos);
pushup(rt);
}
int query(int x,int y,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[y].sum-tree[x].sum;
int mid=(L+R)>>1,val=0;
if(l<=mid)val+=query(tree[x].ls,tree[y].ls,L,mid,l,r);
if(mid<r)val+=query(tree[x].rs,tree[y].rs,mid+1,R,l,r);
return val;
}
struct gra{
int v,next;
}edge[400010];
int tot,head[200010][2];
void add(int u,int v,int id){
edge[++tot].v=v;edge[tot].next=head[u][id];head[u][id]=tot;
}
int num,size[200010][2],dfn[200010][2],rk[200010];
void dfs(int x,int id){
size[x][id]=1;dfn[x][id]=++num;
if(!id)rk[num]=x;
for(int i=head[x][id];i;i=edge[i].next){
dfs(edge[i].v,id);
size[x][id]+=size[edge[i].v][id];
}
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%d%d%s",&n,&q,s+1);
for(int i=1;i<=t;i++)tree[i].ls=tree[i].rs=tree[i].sum=0;t=tot=0;
for(int i=1;i<=n;i++)rt[i]=nxt[i]=0;
for(int i=0;i<=n+1;i++)head[i][0]=head[i][1]=0;
add(0,1,0);
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1])j=nxt[j];
if(s[i]==s[j+1])j++;
nxt[i]=j;add(nxt[i],i,0);
}
for(int i=1;i<=n;i++)nxt[i]=0;nxt[n]=n+1;
add(n+1,n,1);
for(int i=n-1,j=n+1;i>=1;i--){
while(j<n+1&&s[i]!=s[j-1])j=nxt[j];
if(s[i]==s[j-1])j--;
nxt[i]=j;add(nxt[i],i,1);
}
num=0;dfs(0,0);
num=0;dfs(n+1,1);
for(int i=1;i<=n+1;i++)update(rt[i],rt[i-1],1,n+1,dfn[rk[i]+1][1]);
while(q--){
int x,y;scanf("%d%d",&x,&y);y=n-y+1;
printf("%d\n",query(rt[dfn[x][0]-1],rt[dfn[x][0]+size[x][0]-1],1,n+1,dfn[y][1],dfn[y][1]+size[y][1]-1));
}
}
}
计数
也许通过瞪 Rainybunny 老师题解瞪会了 \(O(n^2)\) 做法，感觉十分魔幻。有没有比较自然的解释。憎恨组合意义。
枚举相邻的编号 \(x,y\)，计算它们在多少个序列里出现。有一个神秘的 dp 定义：设 \(dp_{x,y}\) 为考虑 \(\text{lca}(x,y)\) 子树的序列，\(x,y\) 相邻且不区分 \(x,y\) 子树节点的方案数。设 \(lc=\text{lca}(x,y)\)。
我们先处理出 \(x\) 子树内的合法序列个数 \(g_x\)。那么对于 \(fa_x=fa_y=lc\) 时，有
\[dp_{x,y}=\binom{size_{lc}-2}{size_x+size_y-1}\binom{size_{lc}-1-size_x-size_y}{\{size_v|v\in son_{lc}\setminus \{x,y\}\}}\prod_{v\in son_{lc}\setminus\{x,y\}}g_v \]具体说就是别的正常选，\(x,y\) 粘到一起然后剩下 \(size_{lc}-2\) 个空位，把节点插进去。
如果不是直接父亲，那么需要找到父亲然后往下转移。需要确定 \(x\) 的兄弟的顺序：有新的贡献
\[dp_{fa_x,y}\binom{size_{fa_x}+size_y-2}{size_{fa_x}-size_x-1}\binom{size_{fa_x}-size_x-1}{\{size_v|v\in son_{fa_x}\setminus\{x\}\}}\prod_{v\in son_{fa_x}\setminus\{x\}}g_v \]考虑如何统计答案。设 \(ans_{lc}\) 为 \(lc\) 子树的答案。则枚举两个子树内的点并给它们定序，贡献则是
\[ans_{lc}=\sum_{x,y}|x-y|dp_{x,y}g_xg_y\binom{size_x+size_y-2}{size_x-1} \]最后是往上放到根。对父亲的贡献仍然乘上仍然是不同兄弟的顺序，是组合数：
\[ans_x\binom{size_{fa_x}-2}{size_x-1}\dbinom{size_{fa_x}-size_x-1}{\{size_v|v\in son_{fa_x}\setminus\{x\}}\prod_{v\in son_{fa_x}\setminus\{x\}}g_v \]#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
int n,rt,dp[210][210],g[210],fa[210],size[210],jc[210],inv[210],invg[210],ans[210];
int C(int n,int m){
if(n<m||m<0)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int invC(int n,int m){
if(n<m||m<0)return 0;
return 1ll*inv[n]*jc[m]%mod*jc[n-m]%mod;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
struct node{
int v,next;
}edge[410];
int t,head[210];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void dfs1(int x,int f){
size[x]=1;fa[x]=f;
int val=1;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
size[x]+=size[edge[i].v];
val=1ll*val*inv[size[edge[i].v]]%mod*g[edge[i].v]%mod;
}
}
g[x]=1ll*jc[size[x]-1]*val%mod;invg[x]=qpow(g[x],mod-2);
}
int solve(int w,int x,int y){
if(dp[x][y])return dp[x][y];
if(fa[x]==w&&fa[y]==w){
int val=1ll*invC(size[w]-1,size[x])*invC(size[w]-size[x]-1,size[y])%mod;
dp[x][y]=1ll*g[w]*invg[x]%mod*invg[y]%mod*val%mod*C(size[w]-2,size[x]+size[y]-1)%mod;
}
if(fa[x]!=w){
int val=1ll*C(size[fa[x]]+size[y]-2,size[fa[x]]-size[x]-1)*invC(size[fa[x]]-1,size[x])%mod;
dp[x][y]=(dp[x][y]+1ll*g[fa[x]]*invg[x]%mod*val%mod*solve(w,fa[x],y))%mod;
}
if(fa[y]!=w){
int val=1ll*C(size[fa[y]]+size[x]-2,size[fa[y]]-size[y]-1)*invC(size[fa[y]]-1,size[y])%mod;
dp[x][y]=(dp[x][y]+1ll*g[fa[y]]*invg[y]%mod*val%mod*solve(w,x,fa[y]))%mod;
}
return dp[x][y];
}
vector<int>dfs2(int x,int f){
vector<int>ret;
int inv=qpow(size[x]-1,mod-2);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
ans[x]=(ans[x]+1ll*abs(x-edge[i].v)*size[edge[i].v]%mod*g[x]%mod*inv)%mod;
vector<int>tmp=dfs2(edge[i].v,x);
for(int a:ret){
for(int b:tmp){
int val=2ll*abs(a-b)*g[a]%mod*g[b]%mod*C(size[a]+size[b]-2,size[a]-1)%mod;
ans[x]=(ans[x]+1ll*solve(x,a,b)*val)%mod;
}
}
for(int y:tmp)ret.push_back(y);
}
}
ret.push_back(x);
return ret;
}
void dfs(int x,int f){
int inv=qpow(size[x]-1,mod-2);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs(edge[i].v,x);
int val=1ll*g[x]*invg[edge[i].v]%mod*size[edge[i].v]%mod*inv%mod;
ans[x]=(ans[x]+1ll*ans[edge[i].v]*val)%mod;
}
}
}
int main(){
scanf("%d%d",&n,&rt);jc[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(rt,0);
dfs2(rt,0);
dfs(rt,0);
printf("%d\n",ans[rt]);
return 0;
}
数论
大弱智题。
答案是
\[\prod_{i=1}^t\frac{1-x}{1-p_ix} \]的 \(n\) 次项系数。我不想多解释。
int n,t,m,p[100010];
pair<poly,poly> solve(int l,int r){
if(l==r){
poly up(m+1),down(m+1);
for(int i=0,pw=1;i<=m;i++,pw=1ll*pw*p[l]%mod){
up[i]=C(m,i),down[i]=1ll*C(m,i)*pw%mod;
if(i&1){
up[i]=sub(0,up[i]);
down[i]=sub(0,down[i]);
}
}
return make_pair(up,down);
}
int mid=(l+r)>>1;
pair<poly,poly> L=solve(l,mid),R=solve(mid+1,r);
return make_pair(L.first*R.first,L.second*R.second);
}
int calc(int n,poly p,poly q){
int k=p.size();
poly f(k);get(k<<1);
while(n){
for(int i=0;i<k;i++)f[i]=(i&1)?(mod-q[i])%mod:q[i];
f.resize(wl);p.resize(wl);q.resize(wl);
DIF(f);DIF(p);DIF(q);
for(int i=0;i<wl;i++)p[i]=1ll*p[i]*f[i]%mod,q[i]=1ll*q[i]*f[i]%mod;
DIT(p);DIT(q);
p.resize(k);q.resize(k);f.resize(k);
for(int i=0;i<k;i++)p[i]=p[(i<<1)|(n&1)],q[i]=q[i<<1];
n>>=1;
}
return 1ll*p[0]*qpow(q[0],mod-2)%mod;
}
signed main(){
n=read(),t=read(),m=read();init(t*(m+1)+1<<1);
for(int i=1;i<=t;i++)p[i]=read();
pair<poly,poly>pr=solve(1,t);
int ans=calc(n,pr.first,pr.second);
print(ans);puts("");
return 0;
}