【题解】牛客OI周赛14-提高组

A.魔改森林

首先，让我们考虑从点 ${1,1}$ 到点 ${n,m}$ ，只能向下和向右走，经过观察可以发现，无论怎么走，一定是向下走了 $n-1$ 步，向右走了 $m-1$ 步，那么总共走了 $n-1+m-1$ 步，那么方案数为从 $n-1+m-1$ 步中选出 $n-1$ 步，即 $C(n+m-2,n-1)$ 。
回到题目，走的方向不一样，棋盘为格点，那么问题的本质与上述问题一样。
对于没有障碍的，就是以上问题的答案。
对于含有一个障碍的，显然中途我们不能经过障碍，设障碍 ${x,y}$ ，设 $to(x_1,y_1,x_2,y_2)$ 表示从 $x1,y1$ 走到 $x_2,y_2$ 的方案数，那么不合法的方案数为 $to(1,1,x,y)*to(x,y,n,n)$ ，用合法方案数减去不合法的即可。
对于一个以上，也同样可以利用容斥原理解决，但需要注意点的顺序和所在位置的关系。

#include
using namespace std;
typedef long long ll;
const int mod=998244353,N=2e5+5;
ll f[N],invf[N];
int n,m,k,x[4],y[4];
ll C(int n,int m)
{
    if(n<0||m<0) return 0;
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
void solve1()
{
    int a[n+10][m+10];
    ll dp[n+10][m+10];
    memset(dp,0,sizeof(dp));
    memset(a,0,sizeof(a));
    for(int i=1;i<=k;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    dp[n+1][1]=1;
    for(int i=n+1;i>=1;i--)
        for(int j=1;j<=m+1;j++)
        if(!a[i][j])
        {
            (dp[i][j]+=dp[i+1][j])%=mod;
            (dp[i][j]+=dp[i][j-1])%=mod;
        }
    printf("%lld\n",dp[1][m+1]);
}
ll to(int x1,int y1,int x2,int y2)
{
    return C(x1-x2+y2-y1,y2-y1);
}
void solve2()
{
    for(int i=1;i<=k;i++)
        scanf("%d%d",&x[i],&y[i]);
    ll ans=to(n+1,1,1,m+1);
    for(int i=1;i<=k;i++)
        ans-=to(n+1,1,x[i],y[i])*to(x[i],y[i],1,m+1)%mod;
    ans%=mod;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        if(i!=j&&x[j]=y[i])
        ans+=to(n+1,1,x[i],y[i])*to(x[i],y[i],x[j],y[j])%mod*to(x[j],y[j],1,m+1)%mod;
    ans%=mod;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        for(int s=1;s<=k;s++)
        if(i!=j&&i!=s&&j!=s&&x[j]=y[i]&&x[s]=y[j])
        ans-=to(n+1,1,x[i],y[i])*to(x[i],y[i],x[j],y[j])%mod*to(x[j],y[j],x[s],y[s])%mod*to(x[s],y[s],1,m+1)%mod;
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}
int main()
{
    f[0]=invf[0]=f[1]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i-1]*invf[i]%mod;
    scanf("%d%d%d",&n,&m,&k);
    if(n<=1000&&m<=1000) solve1();
    else solve2();
}

B.神经冲动

首先，可以证明给定的状态一定可以达到，有一种实现方案为：
每次选择一个不符合答案状态的深度最大的点，然后刺激这个点。

显然是状压 $dp$ ，但问题在于每个点不能在同一时间内被刺激，因为时间不可冲突，所以我们考虑按时间线来设计 $dp$ 状态，设 $dp_{i,j}$ 表示到了 $i$ 时刻，状态为 $j$ 的方案是否存在，如何转移？新加入一个点，我们设他在 $0$ 时刻被激活，那么到了 $i$ 时刻，这个点经历的时间总量为 $i+1$ ，这个点在 $i+1$ 个时间内对总状态的贡献可以预处理出来，那么就很容易得到了转移。

#include
using namespace std;
const int N=16;
int n,fa[N],st[N],now[N],ans;
bool dp[N<<1][1<<15];
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
    for(int i=1;i<=n;i++)
    {
        now[i]=i;
        int x;scanf("%d",&x);
        if(x) ans|=1<<i-1;
    }
    int up=1<<n;
    dp[0][0]=true;
    for(int i=0;i<=2*n;i++)
    {
        if(dp[i][ans])
        {
            printf("%d\n",i);return 0;
        }
        for(int j=1;j<=n;j++)
            if(now[j]) st[j]|=1<<now[j]-1,now[j]=fa[now[j]];
        for(int j=0;j<up;j++)
            if(dp[i][j])
            {
                for(int k=1;k<=n;k++)
                    dp[i+1][j^st[k]]=true;
            }
    }
}

C:世界线

可以看出每个连通块都是一颗树，对于每颗树，选定一个根，进行一次 $dfs$ 可以得出根结点的答案，然后再换根，在一次从根 $u$ 换到 $v$ 时，距离减少 $dis_{u,v}$ 的点为 $v$ 的子树，其它点距离增大 $dis_{u,v}$ ，差分一下，让子树 $v$ 的距离减少 $2*dis(u,v)$ ，然后枚举子树 $v$ 上的所有结点，注意期望高度为 $logn$ ，所以每次我们每次枚举子树的次数为 $nlog(n)$ ，用线段树或平衡树维护一下，总时间复杂度 $nlog^2n$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
const ll low=-1e15,up=1e15;
ll rt,tot,t[N*100],ls[N*100],rs[N*100];
ll newnode(){tot++;t[tot]=ls[tot]=rs[tot]=0;return tot;}
ll ans[N],dis[N],cf[N];
bool vis[N];
ll n,m,q,si,sum,head[N],nex[N<<1],to[N<<1],wi[N<<1];
void add(ll u,ll v,ll w){to[++sum]=v;nex[sum]=head[u];head[u]=sum;wi[sum]=w;}
vector<pair<ll,ll>>v[N];
void Insert(ll l,ll r,ll x,ll &now,ll v)
{
    if(!now) now=newnode();
    t[now]+=v;
    if(l==r) return;
    ll m=l+r>>1;
    if(x<=m) Insert(l,m,x,ls[now],v);
    else Insert(m+1,r,x,rs[now],v);
}
ll query(ll l,ll r,ll k,ll &now)
{
    if(l==r) return l;
    ll m=l+r>>1;
    if(t[rs[now]]>=k) return query(m+1,r,k,rs[now]);
    return query(l,m,k-t[rs[now]],ls[now]);
}
void dfs(ll u)
{
    si++;
    Insert(low,up,dis[u],rt,1);
    vis[u]=true;
    for(ll i=head[u];i;i=nex[i])
    {
        ll v=to[i];if(vis[v])continue;
        cf[v]=dis[v]=dis[u]+wi[i];
        dfs(v);
    }
}
void vvv(ll u,ll p,ll w)
{
    Insert(low,up,dis[u],rt,-1);
    dis[u]+=w;
    Insert(low,up,dis[u],rt,1);
    for(ll i=head[u];i;i=nex[i])
    {
        ll v=to[i];if(v==p) continue;
        vvv(v,u,w);
    }
}
void dfs(ll u,ll p)
{
    for(pair<ll,ll>x:v[u])
    {
        if(x.first>=si) ans[x.second]=-1;
        else ans[x.second]=query(low,up,x.first,rt)+cf[u];
    }
    for(ll i=head[u];i;i=nex[i])
    {
        ll v=to[i];if(v==p) continue;
        vvv(v,u,-2ll*wi[i]);
        dfs(v,u);
        vvv(v,u,2ll*wi[i]);
    }
}
void solve(ll x)
{
    rt=tot=si=0;
    dfs(x);
    dfs(x,0);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(ll i=1;i<=q;i++)
    {
        ll x,k;scanf("%lld%lld",&x,&k);
        v[x].push_back({k,i});
    }
    for(ll i=1;i<=n;i++)
        if(!vis[i])
    {
        solve(i);
    }
    for(ll i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}