ARC 058 比赛记录（VP）

$\checkmark$ A

给定 $x$ 以及几个 $0\sim 9$ 的数字，求最小的 $k$ 满足 $k\ge x$ 且 $k$ 的十进制表示中不含给定的数字。保证不能出现的数字不是 $0\sim 9$ 或 $1\sim 9$。

直接从 $x$ 开始枚举，检验是否满足要求，记 $t=\lfloor \log_{10} x\rfloor$，则必然 $k<10^{t+1}$。时间复杂度可以接受。

bool vis[15];
inline bool check(int x)
{
    while(x)
    {
        if(vis[x%10]) return false;
        x/=10;
    }
    return true;
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,k;cin>>n>>k;
    for(int i=1,x;i<=k;i++) cin>>x,vis[x]=true;
    while(!check(n)) ++n;
    cout<<n<<endl;
}

$\checkmark$ B

一个 $n\times m$ 的网格图，只能往左往上走，其中左上角 $a\times b$ 的区域不能走，求从 $(1,1)$ 到 $(n,m)$ 的方案数，对 $10^9+7$ 取模。

如果无限制，从 $(x,y)$ 走到 $(z,w)$ 的方案数为 $\binom{z-x+y-w}{z-x}$，可以理解为在 $z-x+y-w$ 步中选择 $z-x$ 步沿着 $x$ 轴方向走。

枚举不可走的矩形的某个方向延长线，则合法的路径必经该延长线，按照上文的方式计算即可。注意如果一条路径如果在延长线上经过多个点可能会导致重复计算。预处理组合数可以做到 $O(n+m)$。

constexpr int N=2e5+5;using ll=long long;constexpr ll mod=1e9+7;
inline ll qpow(ll a,ll b)
{
    ll ret=1;a%=mod;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll fac[N],ifac[N];
inline ll binom(ll n,ll m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline void work()
{
    using namespace IO;
    int n,m,a,b;qread(n),qread(m),qread(a),qread(b);
    int l=n+m;
    fac[0]=ifac[0]=1;
    for(int i=1;i<=l;i++) fac[i]=fac[i-1]*i%mod;
    ifac[l]=qpow(fac[l],mod-2);
    for(int i=l-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    ll ans=0;
    for(int i=1;i<=n-a;i++) ans=(ans+binom(i+b-2,b-1)*binom(n+m-i-b-1,m-b-1)%mod)%mod;
    qwrite(ans),pc('\n');
}

$✗$ C

不大会做。求长度为 $n$ 的序列个数，满足序列中每个数的值域为 $[1,10]$ 且存在一个子区间，使得该子区间能被分为三部分，且三部分的和分别为 $x,y,z$。对 $10^9+7$ 取模。

直接算会算重，考虑正难则反，减去不合法的序列数量。

解题的要点在于设计一个合理的状压。从前往后枚举序列，对于当前枚举的位置从此处计算后缀和，并将每个后缀和对应的二进制为赋为 $1$，则容易判断当前从结尾开始的区间是否能满足条件，如果不满足条件则转移。时间复杂度 $O(n2^{x+y+z})$。

constexpr int N=45,M=(1<<17)+5;using ll=long long;constexpr ll mod=1e9+7;
ll f[N][M];
inline ll qpow(ll a,ll b)
{
    ll ret=1;a%=mod;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
inline void work()
{
    int n,x,y,z;cin>>n>>x>>y>>z;
    int S=(1<<(x+y+z))-1,ist=(1<<(x+y+z-1))|(1<<(y+z-1))|(1<<(z-1));
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=S;j++)
        {
            for(int k=1;k<=10;k++)
            {
                int t=((j<<k)|(1<<(k-1)))&S;
                if((t&ist)==ist) continue;
                f[i][t]=(f[i-1][j]+f[i][t])%mod;
            }
        }
    ll ans=qpow(10,n);
    for(int j=0;j<=S;j++) ans=(ans-f[n][j])%mod;
    cout<<(ans%mod+mod)%mod<<endl;
}

$✗$ D

会个暴力 DP，不太行。给定 $n$ 个字符串，你需要选出一部分进行拼接，不能改变字符串间的相对顺序，求最后能得到长为 $k$ 的字符串字典序最小的。

有个 $O(nk^2)$ 的暴力做法，即设 $f_{i,j}$ 表示前 $i$ 个字符串中，拼为长度为 $k$ 的字符串字典序最小的。转移显然，时空双重爆炸。有个显然的优化是我们可以求出 $g_{i,j}$ 表示在考虑 $i$ 之后已经有了 $j$ 个字符，是否可以拼成长度 $k$ 的字符串，如果 $g_{i,j}$ 为 $0$，则该 DP 之状态是无用的。不过我们似乎没用到字典序的性质。如果我们有 $\texttt{abbc}$ 和 $\texttt{abc}$，则无论在第二个状态后加什么字符都不能比第一种状态优，所以只要状态之间不是前缀关系则必然能比较出优劣，此时只用记录下最长的合法字符串的状态即可，此时空间复杂度转变为 $O(nk)$。现在瓶颈在与字符串比较，我们发现比较的内容为一个字符串的某些后缀和另一个字符串，求出 LCP（最长公共前缀）可做到快速比较。使用二分与 hash 可做到 $O(\log k)$，而使用 Z 函数（exkmp） 可做到单次 $O(1)$。时空复杂度均为 $O(nk)$。代码真的难写。（二分加 hash 的做法貌似被出题人对着卡了）

参考抄袭 zhylj 的代码实现。

constexpr int N=2005,M=1e4+5;
inline void zfunc(string b,int z[])
{
    int n=int(b.length());z[0]=n;
    for(int i=1,l=0,r=-1;i<n;i++)
    {
        z[i]=(i<=r)?min(z[i-l],r-i+1):0;
        while(i+z[i]<n&&b[i+z[i]]==b[z[i]]) ++z[i];
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;
    }
}
inline void exkmp(string&a,string&b,int z[],int p[])
{
    int n=int(a.length()),m=int(b.length());
    zfunc(a,z);
    for(int i=0,l=0,r=-1;i<m;i++)
    {
        p[i]=(i<=r)?min(z[i-l],r-i+1):0;
        while(i+p[i]<m&&p[i]<n&&b[i+p[i]]==a[p[i]])++p[i];
        if(i+p[i]-1>r) l=i,r=i+p[i]-1;
    }
}
string s[M],t[M];bool g[N][M],f[N][M];
struct dat{int x,y;}st[M];int top=0,p[M],z[M];
inline int cmp(int id,dat a,dat b)
{
    int fl=1,res=0;if(a.x<b.x) swap(a,b),fl*=-1;
    int x=b.x,y=a.x;
    if(x+p[x]<y&&p[x]<b.y) res=t[id-1][x+p[x]]<s[id][p[x]]?-1:1;
    else if(z[y-x]<a.y&&y-x+z[y-x]<b.y) res=s[id][z[y-x]]<s[id][y-x+z[y-x]]?-1:1;
    return res*fl;
}
inline void work()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    g[n+1][0]=true;
    for(int i=n;i>0;i--)
    {
        int l=int(s[i].length());
        for(int j=0;j<=m;j++)
        {
            if(j>=l) g[i][j]|=g[i+1][j-l];
            g[i][j]|=g[i+1][j];
        }
    }
    t[1]=s[1],f[1][0]=f[1][s[1].length()]=true;
    for(int i=2;i<=n;i++)
    {
        int l=int(s[i].length());
        memset(z,0,sizeof(z));memset(p,0,sizeof(p));
        exkmp(s[i],t[i-1],z,p);top=0;
        for(int j=0;j<=m;j++)
        {
            if(!g[i+1][m-j]) continue;
            dat now;
            if(j>=l&&f[i-1][j]&&f[i-1][j-l]) now=cmp(i,(dat){j-l,l},(dat){j,0})==-1?(dat){j-l,l}:(dat){j,0};
            else if(j>=l&&f[i-1][j-l]) now=(dat){j-l,l};
            else if(f[i-1][j]) now=(dat){j,0};
            else continue;
            while(top&&cmp(i,now,st[top])==-1) f[i][st[top].x+st[top].y]=false,top--;
            if(!top||!cmp(i,now,st[top])) st[++top]=now,f[i][j]=true;
        }
        t[i]=t[i-1].substr(0,st[top].x)+s[i].substr(0,st[top].y);
    }
    cout<<t[n]<<endl;
}