头像

whsstory

杭州学军中学




离线:5天前



whsstory
1个月前

考虑计算钦定$m$条割边的方案数$f_m$.最后再二项式反演还原。

$f_m$就是缩点后$m+1$个点的树,其中每个点是一个连通图(总点数为$n$)的方案数(如果不用二项式反演就是边双连通图数了,难整)

记$i$个点的连通图数量为$g_i$,有
$$
f_m=\frac{1}{(m+1)!}\sum_{\sum A=n,|A|=m+1} \binom{n}{a_1,a_2…a_{m+1}}n^{m-1}\prod_i a_ig_{a_i}
$$
这里用到一个经典结论:$m$个连通块,大小分别为$a_1,a_2…a_n$,连成的有标号树数量为$(\sum a_i)^{m-2}\prod a_i$,可参见「WC2019」数树

这样加入一个大小为$x$的块的贡献看成$\frac{xg_{x}}{x!}$,直接dp就行了。

注意到$m\ge n-1$时$f_m=0$,所以复杂度是$O(n^3)$.

实际上转移式子是卷积,所以理论上也可以MTT优化到$O(n^2\log n)$.听说利用某些多项式科技可以做到更好?

const int MAXN = 511,mod = 1e9+7;
int f[MAXN][MAXN],g[MAXN],all[MAXN],tp[MAXN];
ll fac[MAXN],inv[MAXN];
ll C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll Qpow(ll a,ll p)
{
    ll res=1;
    while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
    return res;
}
void init(int n)
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;
    inv[n]=Qpow(fac[n],mod-2);
    for(int i=n-1;i;--i)inv[i]=inv[i+1]*(i+1)%mod;

    all[0]=1;
    for(int i=1;i<=n;++i)all[i]=Qpow(2,i*(i-1)/2);
    //Also,G = ln All
    for(int i=1;i<=n;++i)
    {
        g[i]=all[i];
        for(int j=1;j<i;++j)g[i]=(g[i]-C(i-1,j-1)*g[j]%mod*all[i-j])%mod;
    }
}
int main()
{
    int n=read(),m=read(),invn=Qpow(n,mod-2);
    init(n);
    f[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            for(int x=1;x<=j;++x)
                f[i][j]=(f[i][j]+ll(f[i-1][j-x])*inv[x-1]%mod*g[x])%mod;
    for(int i=0;i<n;++i)
    {
        tp[i]=f[i+1][n]*Qpow(n,i)%mod*invn%mod*fac[n]%mod*inv[i+1]%mod;
    }
    int ans=0;
    for(int i=0;i<=min(n-1,m);++i)
    {
        int cur=0;
        for(int j=i;j<=n;++j)
            if((j-i)&1)cur=(cur-C(j,i)*tp[j])%mod;
            else cur=(cur+C(j,i)*tp[j])%mod;
        ans=(ans+cur)%mod;
    }
    printf("%d\n",(ans+mod)%mod);
    return 0;
}




whsstory
1个月前

请问ubuntu下chrome无法显示等宽字体怎么办?更要命的是和光标不能对齐了




whsstory
1个月前

之前一个网友问我这题,当时我不会,可惜我不记得是谁问的了,非常抱歉。


考虑$x$购买,则$y$ 才可以满足$A$,就是在说,若$y$满足$A$,则推出$x$购买。

$x\rightarrow y$并且最大化权值和容易想到最大权闭合子图。

此外还可以关注到,物品$i$的价值$y$是关于$x$的二次函数,那么4段$[0,0],[L_i,L_i],(L_i,R_i),[R_i,R_i]$ 中,0看成没有选择,$(L_i,R_i)$看成一个点$i_1$,$L_i,R_i$看成一个点$i_2$。

$i_1$的点权定义为那三段的最大值,$i_2$的点权定义为$L_i,R_i$的最大值减去$i_1$点权,并令$i_2$向$i_1$连边,这样就给出物品$i$的4种情况(此时又选$i_1$又选$i_2$表示选$L_i$或$R_i$的最大值)。

剩下的连边就很简单了,对于第一种,$y_1$连向$x_1$,对于第二种$y_2$连向$x_1$

最后就是一个最大流。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
typedef long long ll;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 200011;
const ll INF=1e18;
struct edge{int v,nxt;ll w;}e[MAXN<<2|1];
int cnt=1,last[MAXN],cur[MAXN];
void add_directed_edge(int u,int v,ll w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(int u,int v,ll w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}

int dep[MAXN],Q[MAXN];
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)dep[i]=0,cur[i]=last[i];
    int qh=0,qt=0;
    Q[qt++]=s,dep[s]=1;
    while(qh<qt)
    {
        int u=Q[qh++];
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(!dep[v]&&e[i].w)dep[v]=dep[u]+1,Q[qt++]=v;
        }
    }
    return dep[t];
}
ll ex_flow(int u,int t,ll flow=INF)
{
    if(u==t)return flow;
    ll f=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
ll Dinic(int s,int t,int n)
{
    ll res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
ll A,B,C,val[MAXN];
inline ll f(ll x){return A*x*x+B*x+C;}
int main()
{
    int n=read(),m=read(),S=2*n+1,T=S+1;
    for(int i=1;i<=n;++i)
    {
        ll L=read(),R=read();
        A=read(),B=read(),C=read();
        ll f1=-INF,f2=max(f(L),f(R));
        for(int j=L+1;j<R;++j)umax(f1,f(j));
        val[i]=f1,val[n+i]=f2-f1;
        adde(n+i,i,INF);
    }
    while(m--)
    {
        int t=read(),x=read(),y=read();
        if(t==1)adde(y,x,INF);
        else adde(n+y,x,INF);
    }
    ll ans=0;
    for(int i=1;i<=n+n;++i)
        if(val[i]>0)ans+=val[i],adde(S,i,val[i]);
        else adde(i,T,-val[i]);
    printf("%lld\n",ans-Dinic(S,T,T));
    return 0;
}




whsstory
2个月前

整数线性规划与全幺模矩阵

全幺模矩阵(totally unimodular matrix)是指任何一个行数和列数相等的满秩子矩阵行列式的值都是1或-1的矩阵。

其意义在于,若$\mathbf {A}$为全幺模矩阵, 对线性规划
$$
\mathbf{Ax}\le \mathbf{b,x\ge 0}\\
\text{Maximize }\sum c_ix_i
$$
执行单纯性法过程中涉及的所有约束的系数$\in{-1,0,1}$. 那么$x_i$限制为实数和限制为${0,1}$ 时答案相同。即这样的整数线性规划(整数线性规划本身为NP问题,单纯形法亦无法求解)的答案与实数线性规划的答案相同。同样套用单纯形法即可(均为整数还可以优化常数)

考虑此题怎么变成线性规划。

由题意得:
$$
\sum_{L_j\le i\le R_j}x_j\ge a_i(i\in[1,n])\\
x_i\ge 0\\
\text{Minimize} \sum_ic_ix_i
$$

对偶之后得:
$$
\sum_{L_i\le j\le R_i}x_j\le c_i(i\in [1,m])\\
x_i\ge 0\\
\text{Maximize} \sum a_ix_i
$$

单纯性直接上就好了,能过的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
double fabs(double x){return x>0?x:-x;}
bool is_zero(double x){return x<1e-7&&-x<1e-7;}
/**********/
const int MAXN = 1011,MAXM = 10011;
//LP on {-1,0,1}
int a[MAXM][MAXN],n,m;
int dex[MAXM<<1|1];
void pivot(int B,int N)
{
    if(!a[B][N]){std::cerr<<"ERR!";exit(-5);}
    int rate=a[B][N];
    //printf("Rate=%d\n",rate);
    a[B][N]=1;
    for(int j=0;j<=n;++j)a[B][j]*=rate;
    for(int i=0;i<=m;++i)
        if(i!=B)
        {
            int rate=a[i][N];
            if(!rate)continue;
            a[i][N]=0;
            for(int j=0;j<=n;++j)a[i][j]-=a[B][j]*rate;
        }
    //std::swap(dex[m+B],dex[N]);
}
void prt()
{
    puts("Prt:");
    for(int i=0;i<=m;++i,puts(""))
        for(int j=0;j<=n;++j)printf("%d ",a[i][j]);
}
int simplex()
{
    //prt();
    while(1)
    {
        int B=-1,N=-1;
        for(int i=1;i<=n;++i)
            if(a[0][i]>0){N=i;break;}
        if(N<0)break;
        int minv=1e9;
        for(int i=1;i<=m;++i)
            if(a[i][N]==1&&umin(minv,a[i][0]))B=i;
        if(B<0){return 1e9+233;}
        pivot(B,N);
        //prt();
    }
    return -a[0][0];
}
int need[MAXN];
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)need[i]=read(),a[0][i]=need[i];
    for(int i=1;i<=m;++i)
    {
        int l=read(),r=read(),c=read();
        for(int j=l;j<=r;++j)a[i][j]=1;
        a[i][0]=c;
    }
    printf("%d\n",simplex());
    return 0;
}




whsstory
2个月前

联合省选2021 完整题解

详略程度和难度无关。

A卷 Day1T1 卡牌游戏

考虑枚举最小值$minv$($minv$一定是某个$a$或$b$,排序之后枚举即可).此时只需令最大值最小即可(当然要满足$m$的限制)。

为了满足最小值的限制,我们要翻一个前缀$[1,Lt]$.显然$Lt$关于$minv$非严格增。注意特判翻出的$b<minv$的情况。

为了令最大值最小,我们要翻一个后缀$[Rt,n]$.注意$Rt$要满足$m$和$minv$的限制。

考虑比较$[Rt,n]$和$[Rt+1,n]$.前者导致的最大值是$max(Sufmax_{Rt},a_{Rt-1})$,后者导致的最大值是$max(Sufmax_{Rt+1},a_{Rt})$.如果后者更小则增加$Rt$即可(注意同样优时也要增加$Rt$, 因为可能这个函数有一段平的,之后的某个位置才变小)

此外,当$minv$增大时$Rt$的下界会增大,其余不变,因此最优的$Rt$也是非严格增的,在上一个的基础上继续往右走即可。

瓶颈在于排序,为$O(n\log n)$或$O(n)$

My code

A卷 Day1T2 矩阵游戏

首先构造一个符合和的限制但不符合值域限制的矩阵$M$.这是很容易的,钦定第一行与第一列均为0 ,其余便可唯一推出。

考虑能怎样修改使其合法。为了使和的限制不被破坏,一定是若干次(可能为负)以下两种操作:

  • 对某一行,奇数列+1,偶数列-1
  • 对某一列,奇数行+1,偶数行-1

这样就简单了,设第$i$行操作$x_i$次,第$j$列操作$y_j$次,每个位置$(i,j)$的限制形如:
$$
\begin{align}
M_{i,j}+x_i+y_j\in[0,10^6]\quad (1,1)\\
M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,0)\\
M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\
M_{i,j}-x_i-y_j\in[0,10^6]\quad (0,0)\\
\end{align}
$$
$(1,1)$表示$i,j$都为奇数,其余同理。
恭喜,这样是没法做的

接下来是难以想到的操作:将$x_i,y_j$略作修改,具体的,对$i\mod 2=1,x_i:=-x_i$,对$j\mod 2=0,y_j:=-y_j$.这样操作之后,限制形如:
$$
\begin{align}
M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,1)\\
M_{i,j}+x_i-y_j\in[0,10^6]\quad (1,0)\\
M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\
M_{i,j}-x_i+y_j\in[0,10^6]\quad (0,0)\\
\end{align}
$$
都是两个变量的差的不等式,可以转化为差分约束模型求解,以$M_{i,j}-x_i+y_j\ge 0$为例:$\Rightarrow y_j+M_{i,j}\ge x_i$,令第$j$列代表的点向第$i$行代表的点连边权为$M_{i,j}$的边。

或者你也可以先猜到是用差分约束,然后把初始形式转化为差分约束的形式。

复杂度即$O(Check_Negative_Ring(n+m,nm))$ 。用spfa/Floyd 实现即可。

My code

A卷D1T3 图函数

考虑有序对$(u,v)$在$G$中产生贡献的条件:存在一个环$R$经过$u,v$且$u$为$R$上编号最小的。

进一步,若求出$T(u,v)$表示所有$R$中边的编号最小值最大的,那么$(u,v)$会对所有$i\le T(u,v)$的$G_i$产生贡献。

考虑如何求$T(u,v)$.

我的做法是,考虑Floyd的过程是加入中转点$k$,且加入$S$中所有点作为中转点后,我们求出的最短距离$dis(u,v)$表示$u$到$v$只经过$S\cup{u,v}$中的点的所有路径中边的编号最小值的最大值。

那么,若从大到小加入$k$,此时$(u,v)$的路径上所有点编号都$\ge k$.枚举$v\ge k,T(k,v)=\min(dis(k,v),dis(v,k))$.

时间复杂度$O(n^3)$,但循环展开之后能过!

也有$O(nm)$的做法,大致思路类似。

My code(Floyd)

A卷 Day2T1 宝石

关注$P_i$互不相同 的性质。这个性质指出,如果起点在$u$的子树内且匹配到了$u$且终点为根,那么下一个匹配点是唯一确定的(上一个也是)。因此,下$x$个匹配点也是唯一确定的。预处理每个点往上第一个匹配$P_1$的点$u$,然后可以倍增找出最多能匹配的数量,这样就$O(n\log c)$预处理,$O(\log c)$每次查询的复杂度解决了链上的问题。

对于一般情况,$s\rightarrow LCA$的部分同样可以这样处理,记匹配到$p$。对于$LCA\rightarrow t$的部分,考虑二分答案。设当前要判断能否匹配$[p+1,k]$ .先离线求解$t$往上第一个匹配$P_k$的点,然后同样倍增(这个倍增是倍增前驱)找出最多能匹配的位置$q$,若$q\le p+1$即可。

预处理$O(n\log c)$,$O(\log^2 c)$每次查询。

My code

A卷 Day2T2 滚榜

先考虑暴力枚举所有排列。我们可以考虑贪心,最小化封榜后过题数$t$:若$t(t\le m)$可行,那么一定可以让最后一队再过$m-t$题,这样仍可行。这样是$O(n!n)$的

优化也很显然,考虑状压DP。

暴力是,$f(S,i,w,sum)$表示用了集合$S$,最后一个是$i$,$i$额外过了$w$题,$S$额外过题数和为$sum$.

这样是$O(2^nn^2m^2)$,不太行。

按照套路,$w$是没用的,我们直接费用提前计算,就是说加入一个$j$,若$j$至少要过$x$题,那么之后共有$(n-|S|)$个人要因为$j$再过$x$题。

这样就是$O(2^nn^2m)$了,空间$O(2^nnm)$.

实际上,$\sum_i\binom{n}{i}i(n-i)=2^{n-2}n(n-1)$,计算量至多159744000,是合理的
My code

A卷Day2T3 支配

先求支配树$DT$。

当然可以用polylog的方法,但没必要,枚举删掉点$u$再从1开始bfs,走不到的就受$u$支配,这样就能$O(n(n+m))$求出每个点的支配集;又由于$fa_u$的受支配集大小恰为$u$的受支配集大小减1,就可以$O(n(n+m))$求出$DT$。

考虑一个点$u$,$DT$上父亲为$fa$,受支配集$D_u$变化仅当$D_{fa}$改变或$fa$不再支配$u$.这个等价于若$fa$不再支配$u$,则$u$子树中所有点受支配集都改变。

所以只需判断$fa$是否仍然支配$u$.

记新加入的边为$(x,y)$,那么$fa$不再支配当且$u$仅当原图存在$1\rightarrow x$和$y\rightarrow u$的路径且均不经过$fa$(注意$x,y\ne fa$)。

存在$1\rightarrow x$不经过$fa$显然仅当$fa$不支配$x$.考虑预处理$f(i,j)$表示在不经过$fa_i$的情况下$j$能否到达$i$.那么存在$y\rightarrow u$仅当$f(u,y)=1$.直接在反图上从$i$开始bfs即可预处理好。

询问时候枚举所有$u$判断即可。

总复杂度$O(n(n+m+Q))$

可能轻微卡常,但这些技巧显然省选选手都能掌握。

My code

B卷 数对

枚举$i$的所有倍数的复杂度是$O(A/i)$,去重之后复杂度是$O(\sum_i A/i)=O(A\log A)$.

B卷 取模

我居然这种题都不会了。。。

考虑暴力枚举$k$. 令$b_i=a_i\mod a_k$,就是找一对$b_i+b_j$最大,贡献$(b_i+b_j)\mod a_k$,或找一对$b_i+b_j<a_k$,贡献$b_i+b_j$.将$b$排序后双指针即可。复杂度$O(n^2\log n)$.

然而只要加上两个优化,当$a_k$小于当前答案时直接结束,则不同的有效$a_k$至多$O(\log A)$个。

证明也很容易:记最终答案为$ans$.$a_k$之后两个不同的数为$a_{k+1},a_{k+2}$
$$
(a_{k+1}+a_{k+2})\mod a_k\le ans\\
\Rightarrow a_{k+1}+a_{k+2}-a_k\le ans\\
\Rightarrow (a_{k+1}-ans)+(a_{k+2}-ans)\le a_k-ans
$$
所以数列$f_i=a_i-ans$是至少是斐波那契级别增长,因此不同的有效$k$至多$O(\log A)$个。

总时间复杂度$O(n\log n\log A)$

My code



活动打卡代码 AcWing 2863. 最短路

whsstory
2个月前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 200011;
struct Graph
{
    struct edge{int v,nxt;ll w;}e[MAXN<<1|1];
    int cnt=1,last[MAXN];
    void adde(int u,int v,ll w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
}G,T;
#define from(G,u) for(int i=G.last[u],v=G.e[i].v;i;i=G.e[i].nxt,v=G.e[i].v)
int tot;
int dfn[MAXN],cur=0;
int fa[MAXN];
ll fw[MAXN],d[MAXN],sum[MAXN];
void make_cir(int st,int ed,ll w)
{
    sum[++tot]=w;
    for(int v=st;v!=ed;v=fa[v])d[v]=sum[tot],sum[tot]+=fw[v];
    T.adde(ed,tot,0);
    for(int v=st;v!=ed;v=fa[v])T.adde(tot,v,min(d[v],sum[tot]-d[v]));
}
void dfs1(int u,int preE)
{
    dfn[u]=++cur;
    from(G,u)
    {
        if((i>>1)==preE)continue;
        if(!dfn[v])fa[v]=u,fw[v]=G.e[i].w, dfs1(v,i>>1);
        else if(dfn[v]<dfn[u])make_cir(u,v,G.e[i].w);
    }
}
int Tfa[MAXN],size[MAXN],ms[MAXN],top[MAXN],dep[MAXN];
ll dis[MAXN];
void dfs2(int u)
{
    size[u]=1;
    from(T,u)
    {
        dis[v]=dis[u]+T.e[i].w;
        Tfa[v]=u,dep[v]=dep[u]+1,dfs2(v),size[u]+=size[v];
        if(size[v]>size[ms[u]])ms[u]=v;
    }
}
void dfs3(int s)
{
    for(int u=s;u;u=ms[u])
    {
        top[u]=s;
        from(T,u)
            if(v!=ms[u])dfs3(v);
    }
}
int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>=dep[top[v]])u=Tfa[top[u]];
        else v=Tfa[top[v]];

    }
    return dep[u]>dep[v]?v:u;
}
int top_son(int u,int v)
{
    while(top[u]!=top[v])
        if(Tfa[top[u]]==v)return top[u];
        else u=Tfa[top[u]];
    return ms[v];
}
int main()
{
    int n=read(),m=read(),Q=read();
    for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();G.adde(u,v,w),G.adde(v,u,w);}
    tot=n;
    dfs1(1,0);
    for(int i=1;i<=tot;++i)
        if(!d[i]&&fa[i])T.adde(fa[i],i,fw[i]);
    dfs2(1),dfs3(1);
    while(Q--)
    {
        int u=read(),v=read();
        int p=LCA(u,v);
        if(p<=n)printf("%lld\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
        else
        {
            int X=top_son(u,p),Y=top_son(v,p);
            ll del=abs(d[X]-d[Y]);
            printf("%lld\n",dis[u]-dis[X]+dis[v]-dis[Y]+min(del,sum[p]-del));
        }
    }
    return 0;
}



活动打卡代码 AcWing 3020. 建筑师

whsstory
2个月前

以$n$为分界点,分为$A+B-2$个部分。
一个大小为$x$的部分贡献是$(x-1)!$,对应第一类斯特林数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long ll;
typedef std::vector<int> P;
typedef unsigned un;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
using std::min;
using std::max;
template<typename T>bool umin(T& a,T t){if(a>t)return a=t,1;return 0;}
template<typename T>bool umax(T& a,T t){if(a<t)return a=t,1;return 0;}

const int MAXN = 111,mod = 1e9+7;
int C[211][211],S[50011][211];
void init()
{
    C[0][0]=1;
    for(int i=1;i<=200;++i)
    {
        C[i][0]=1;
        for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    S[0][0]=1;
    for(int i=1;i<=50000;++i)
    {
        for(int j=1;j<=min(i,200);++j)S[i][j]=(S[i-1][j-1]+ll(S[i-1][j])*(i-1))%mod;
    }
}
int main()
{
    init();
    int task=read();
    while(task--)
    {
        int n=read(),A=read(),B=read();
        printf("%lld\n",ll(C[A+B-2][A-1])*S[n-1][A+B-2]%mod);
    }
    return 0;
}





whsstory
2个月前

DP新解与DP套DP技术

先简单介绍一下理解DP的另一个角度.

假设我们要处理一个问题,无论是最优化或是计数问题.搜索的策略是,枚举所有可能的情况,因此复杂度通常为指数级;DP的策略是,将满足某种”共同特征”的所有方案看作一个整体状态,只保留这个整体的最优值/方案数/概率期望 等信息,并通过已知状态推出其他状态,若这种”共同特征”确定得当,则复杂度便可降为多项式级别.

譬如在背包问题中,对于体积和为$x$的所有方案,我们只保存其最优值.

此外,这种理解也符合计数DP也算DP,而单纯的斐波那契数列递推等不算DP这个预期.

下面谈一谈DP套DP技术.这里以「ZJOI2019」麻将 为例.

首先,对所有可能的麻将排列,我们只关注麻将的数量,以及这些麻将是否(存在一个子集)能胡.但是,发现对于两组麻将,很难确定一个”共同特征”.

这是因为,判定麻将是否能胡,并不是极为容易.事实上仅仅是判定,我们就需要一个DP.

比如,设$f(i,x,y,0/1)$表示考虑到第$i$种牌,第$i-1$种牌还剩$x$张,第$i$种牌还剩$y$张,且有/没有 对子时最大的面子数量,$g(i)$表示考虑到第$i$张牌,不同的对子数量.或者也可以设$f(i,x,y,0/1)$表示考虑到第$i$张牌,且$i-1$开头的顺子有$x$个,$i$开头的顺子有$y$个,且有/没有 对子时最大的面子数量,$g(i)$同上.最后若存在一种方案满足有对子且面子至少4个,或者有至少七对对子即可胡. 两种DP都可行,只有常数上的差距.

首先忽略$i$,对后续转移没有影响;对于两组麻将$P,Q$,若$\forall(x,y,k),f_P(x,y,k)=f_Q(x,y,k),g_p=g_Q$($f_P$表示对$P$做上述DP得到的结果,$f_Q$同理),那么无论之后接上什么麻将,之后的DP值都相同,是否胡牌当然也相同了.那么可以尝试,将这个DP的内容,做为一个”共同特征”.可惜的是这样做复杂度难以接受:可能的DP值数量太多,作为状态会导致复杂度无法接受.

我们再从另外一个视角看DP.设给定一个输入序列$P$,求得$f_P$.现在要在$P$后加入一个元素$x$,求得$f_{P+x}$.其实就是从一个状态走到了另一个状态,宏观上看恰如DFA(DFA即确定性有限状态自动机,不熟悉的读者可参考网上资料或参考文献1)上从一个点走到另一个点.说的详细些就是,对这个DP,我们有一个DFA,DP每一种可能的状态都对应DFA上的一个点,DP的转移对应DFA的边,对于给定的输入序列$P$,就是从DFA的起始状态开始走,经过一条链最终走到一个节点,其代表的状态就是我们所求.

对这样一个判断是否能胡的DP,我们也建立一个DFA.所有可能的麻将序列都对应DFA上一条链.另外维护一下每个点能不能胡.这样做的意义在于,虽然可能的麻将序列,可能的DP值数量很多,但若钦定$f$的值不超过4,$g$的值不超过7,这个DFA的节点却比较少:根据实现方法不同,有1500~4000个点(但似乎用第一种DP可能会有9000+的点?)

于是,我们可以直接用DFA的点来表示一个DP状态了.最后求答案的DP是,$f(i,j,p)$表示考虑前$i$种牌,选了$j$张,对应在DFA的节点$p$时的方案数.转移时枚举$i$种选了几张即可(注意同种牌中也是有编号的,还要乘上选出几张的组合数).将第$j$张牌才胡(贡献应为$j$)转化为$1…j$张牌都有1的贡献,答案为:
$$
\frac{\sum_{j=14}^{4n}\sum_{p\not\in Win}f(n,j,p)(j-13)!(n-j)!}{(4n-13)!}
$$
时间复杂度$O(n^2m),m$为DFA的节点数.这种技术称为DP套DP技术.

参考代码:https://loj.ac/s/1115773

此外,徐哲安学长指出,通过DFA最小化技术,可以将DFA缩小至只有200~300个点,详情可见其论文(参考文献1)

参考文献:

  1. 徐哲安,浅谈有限状态自动机及其应用,2021年集训队论文



whsstory
3个月前

从 分级 一题的更优做法谈保序回归问题

给一个序列$y_i$.你要求一个序列$f_i$. 给一个DAG描述一个偏序关系,若有$u\rightarrow v$的路径,则要求$f_u\le f_v$. 给定$p$,最小化:
$$
\sum_{i=1}^n|f_i-y_i|^p(1\le p<\infty)\\
\max_{i=1}^n|f_i-y_i|(p=\infty)
$$
此类问题称为$L_p$问题,也称为 保序回归问题

定义 一个集合$S$的$L_p(1\le p<\infty)$均值为最小化$\sum_{x\in S}|k-y_s|^p$的$k$.

分级 (acwing 273)

给定一个序列$A$.构造一个非严格单调增(或非严格单调减)的序列$B$,最小化$\sum_{i=1}|A_i-B_i|$

原范围$n\le 2000$,可做到$n\le 3\times10^5$

首先我们只处理非严格单调增,因为非严格单调减只需将序列翻转后再做一次.那么我们只需处理序列上的$L_1$问题.

性质:集合$S$的中位数是其$L_1$均值(之一).

引理:对于序列上的$L_p(1\le p<\infty)$问题,若有$y_i>y_{i+1}$那么一定存在一组最优解$F$满足$f_i=f_{i+1}$

$L_1$时候证明很容易,若有$f_i<f_{i+1}$那么将$f_i$改为$f_{i+1}$会更优.

那么我们得到如下解法:

  1. 维护一个单调栈,保存形如$(l,k)$的二元组,表示一个左端点在$l$的区间(右端点不必存,就是下一个左端点-1),且$f$值均为$k$.
  2. 从左往右对于每个$i$,在栈顶加入$(i,a_i)$,若栈顶两个元素$(l_1,k_1),(l_2,k_2)\ (l_1<l_2)$不满足 $k_1>k_2$那么将他们都弹掉,并将$(l_1,k’)$加入栈顶($k’$为$[l_1,i]$的$L_1$均值).

用主席树求区间的中位数,即可做到$O(n\log n)$的复杂度.

参考代码

剩余内容先鸽着吧,以后再补.

参考文献:

高睿泉, 浅谈保序回归问题, 国家集训队2018论文集




whsstory
3个月前

啊,他一个多组数据,一个取模,我都放过去了啊,没想到他,不讲武德,来骗,来卡常!

稍微讲一下怎么卡常,解法就不说了。

首先复杂度是$O(nm\log n)$没法再优化了。
考虑取模是慢的。希望能只做$O(nm)$次取模,即树状数组中不取模。 令树状数组中每个节点都用ull存储信息,加的时候先取模再加,询问的时候取一次模。
不要做$O(nm)$次二分,应该在dp前就完全离散化掉。

参考代码:My Code

一点感想:实际上在省选及以上的比赛中,卡常技巧是必然要掌握的。蓝书作为主要面向联赛层面的书籍,很少提及这方面的内容,因此大家会对此感到不太适应。

什么LCT跑2e6,一个根号跑5e5,3log跑3e5之类的