20210620省队互测-qwaszx 题解

· · 个人记录

T1

其他四重原题分别是

Codechef FRBSUM

FJOI2016 神秘数

19 ICPC 徐州 H

21 ICPC 昆明 M

其中徐州那个是带修的，其他是不带修的. 不带修的情况下通过分散层叠和线性 rmq 我们可以做到 \Theta(n+q\log V)，下面只讨论带修的.

首先考虑静态全局询问情况下如何求出答案，从小到大排序，依次加入，维护当前能表示的极长前缀 [0,sum]. 如果将要加入的元素 x<=sum+1，那么应该把 sum 更新为 sum+x；否则，sum+1 这个元素以后不可能被表示了，这就是答案.

一个自然的想法是暴力做这个过程，每次加入所有 <=sum+1 的数. 由于在停下来之前每两轮 sum 至少乘二，这个过程至多进行 O(\log V) 轮. 用树套树维护区间内小于等于某个值的数的个数，我们就获得了一个三个 \log（可以除个 \log\log）的优秀做法.

上面这个做法看起来没什么救，我们考虑把值域按 [2^i,2^{i+1}) 分块，那么每次要么获得这个块里所有数要么停下. 所以我们只需要维护每个块的 \min 以及 \operatorname{sum}. 朴素实现是 O(n\log V+m\log n\log V)，空间 O(n\log V)，已经足以通过. 一个简单的优化是把底层按 \log V 分块，这样线段树节点只需要 O(n/\log V) 个，空间复杂度达到线性，建树复杂度降至 O(n).

下面认为 V=n^{O(1)}. 由于修改复杂度是 O(\log n) 而查询复杂度是 O(\log^2n)，我们可以使用 O(\log n/\log\log n) 叉的线段树，这样时间复杂度降至 O(n+m\log^2n/\log\log n). 当然这个做法大概只有理论上的意义.

代码是线性空间的做法.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=1e9+500;
const int N=530000;
struct Node
{
    long long s[30];int mi[30];
    Node(){}
    Node(const int &x)
    {
        int id=31-__builtin_clz(x);
        for(int i=0;i<30;i++)s[i]=0,mi[i]=INF;
        s[id]=mi[id]=x;
    }
    void clear(){for(int i=0;i<30;i++)s[i]=0,mi[i]=INF;}
}a[(N/30)<<1];
int n,w[N],qn;
Node operator +(const Node &a,const Node &b)
{
    Node ans;
    for(int i=0;i<30;i++)ans.s[i]=a.s[i]+b.s[i];
    for(int i=0;i<30;i++)ans.mi[i]=min(a.mi[i],b.mi[i]);
    return ans;
}
void build(int rot,int lt,int rt)
{
    if(rt-lt+1<=32)
    {
        a[rot].clear();
        for(int i=lt;i<=rt;i++)
        {
            int id=31-__builtin_clz(w[i]);
            a[rot].s[id]+=w[i],a[rot].mi[id]=min(a[rot].mi[id],w[i]);
        }
        return;
    }
    if(lt==rt){a[rot]=Node(w[lt]);return;}
    int mid=(lt+rt)>>1;
    build(rot<<1,lt,mid),build(rot<<1|1,mid+1,rt);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
void update(int rot,int lt,int rt,int q,int tw)
{
    if(rt-lt+1<=32)
    {
        a[rot].clear();
        w[q]=tw;
        for(int i=lt;i<=rt;i++)
        {
            int id=31-__builtin_clz(w[i]);
            a[rot].s[id]+=w[i],a[rot].mi[id]=min(a[rot].mi[id],w[i]);
        }
        return;
    }
    int mid=(lt+rt)>>1;
    if(q<=mid)update(rot<<1,lt,mid,q,tw);
    else update(rot<<1|1,mid+1,rt,q,tw);
//  int id=31-__builtin_clz(tw);
//  a[rot].s[id]=a[rot<<1].s[id]+a[rot<<1|1].s[id];
//  a[rot].mi[id]=min(a[rot<<1].mi[id],a[rot<<1|1].mi[id]);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
Node query(int rot,int lt,int rt,int lq,int rq)
{
    if(rt-lt+1<=32)
    {
        Node ans;ans.clear();
        for(int i=max(lt,lq);i<=rt&&i<=rq;i++)
        {
            int id=31-__builtin_clz(w[i]);
            ans.s[id]+=w[i],ans.mi[id]=min(ans.mi[id],w[i]);
        }
        return ans;
    }
    if(lt>=lq&&rt<=rq)return a[rot];
    int mid=(lt+rt)>>1;
    if(rq<=mid)return query(rot<<1,lt,mid,lq,rq);
    if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq);
    return query(rot<<1,lt,mid,lq,rq)+query(rot<<1|1,mid+1,rt,lq,rq);
}
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int main()
{
//  freopen("data.txt","r",stdin);
//  freopen("cswa.txt","w",stdout);
    n=getin(),qn=getin();
    for(int i=1;i<=n;i++)w[i]=getin();
    build(1,1,n);
    for(int i=1,opt,l,r;i<=qn;i++)
    {
        opt=getin(),l=getin(),r=getin();
        if(opt==1)update(1,1,n,l,r);
        else
        {
            Node t=query(1,1,n,l,r);
            long long sum=0;
            for(int j=0;j<30;j++)
            {
                if(!t.s[j])continue;
                if(t.mi[j]<=sum+1)sum+=t.s[j];
            }
            printf("%lld\n",sum+1);
        }
    }   
}

T2

定义一个 1,2,\cdots,n 的排列是好的,当且仅当不存在长为 m 的连续段,使得其中相邻两项的差的绝对值为 1.

给定 n,m,求好排列的数量对 10^9+7 取模的结果.

原题来自一轮集训 nealchen 的课件，把 n 从 5000 加到 5\times 10^6

所求即用长度小于 m 的极长连续段拼出长为 n 的排列的方案数. 为了容斥掉极长的限制,我们为每个长度的连续段赋予一个容斥系数. 设 f_i 为容斥系数,设 F 为 \{f\} 的 OGF,那么我们知道一个长度为 l 的极长连续段的贡献系数为 [x^l]\dfrac{1}{1-F}. 我们应该让其等于 [l<m],这就导出

\frac{1}{1-F}=\sum_{i=0}^{m-1}x^i

解出 F=\dfrac{x-x^m}{1-x^m}. 现在我们可以忽略掉极长的限制,直接进行拼接. 现在一个连续段的贡献 OGF 为

G=[x^1]F+\sum_{i\geq 2}[x^i]2F=\frac{x-2x^m+x^{m+1}}{1-x^m}

我们枚举段数 i,然后有 i! 种方案为所有段赋予权值,也就是说答案的 OGF为

\sum_{i\geq 0}i!G^i

现在我们只需要知道如何快速计算上式. 令

H(x)=\sum_{i\geq 0}i!x^i

那么我们要计算 H(G). 由于 H 是超几何函数所以微分有限,G 是代数的,所以我们知道 H(G) 微分有限. 现在我们来求出 ODE. 首先根据整式递推得到 H 的 ODE:

x^2H'(x)=(1-x)H(x)-1

代入 G 就有

G^2H'(G)=(1-G)H(G)-1

令 u=H(G),我们有 u'=H'(G)G',代入上式可得 u 的 ODE. 由于 ODE 太长,建议使用机器计算.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<vector>
#include<algorithm>
using namespace std;
const int mod=1000000007;
const int N=5e6+500;
int qmod1(const int &x){return x>=mod?x-mod:x;}
int qmod2(const int &x){return x+(x>>31&mod);}
int n,m;
int f[N];
typedef vector<pair<int,int> > Poly;
Poly a1,a2,a3,A,B;
Poly simplify(Poly tans)
{
    sort(tans.begin(),tans.end());
    Poly ans;
    for(int i=0;i<tans.size();i++)
    {
        if(!tans[i].second)continue;
        if(!ans.size()||tans[i].first!=(--ans.end())->first)
            ans.push_back(tans[i]);
        else
        {
            (--ans.end())->second=qmod1((--ans.end())->second+tans[i].second);
            if(!(--ans.end())->second)ans.pop_back();
        }
    }
    return ans;
}
Poly Der(const Poly &a)
{
    Poly ans;
    for(int i=0;i<a.size();i++)
        if(a[i].first)ans.push_back(make_pair(a[i].first-1,1ll*a[i].first*a[i].second%mod));
    return ans;
}
Poly operator -(const Poly &a,const Poly &b)
{
    Poly tans=a;
    for(int i=0;i<b.size();i++)tans.push_back(make_pair(b[i].first,qmod2(-b[i].second)));
    return simplify(tans);
}
Poly operator *(const Poly &a,const Poly &b)
{
    Poly tans;
    for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++)
        tans.push_back(make_pair(a[i].first+b[j].first,1ll*a[i].second*b[j].second%mod));
    return simplify(tans);
}
Poly operator >>(const Poly &a,const int &b)
{
    Poly ans;
    for(int i=0;i<a.size();i++)
        ans.push_back(make_pair(a[i].first-b,a[i].second));
    return ans;
}
void print(const Poly &a)
{
    for(int i=0;i<a.size();i++)
    {
        if(i)putchar('+');
        printf("%d",a[i].second);
        if(a[i].first)printf("x^%d",a[i].first);
    }
    puts("");
}
int main()
{
    freopen("data.txt","r",stdin);
    freopen("cswa.txt","w",stdout);
    scanf("%d%d",&n,&m);
    A.resize(3);
    A[0]=make_pair(1,1),A[1]=make_pair(m,mod-2),A[2]=make_pair(m+1,1);
    B.resize(2);
    B[0]=make_pair(0,1),B[1]=make_pair(m,mod-1);
    a1=A*A*B;
    a2=(B-A)*(Der(A)*B-A*Der(B));
    a3=B*(A*Der(B)-B*Der(A));
    for(int i=0;i<a3.size();i++)
    {
        if(a3[i].first>n)break;
        f[a3[i].first]=qmod2(-a3[i].second);
    }
//  print(a1),print(a2),print(a3);
    for(int i=0;i<=n;i++)
    {
        int t=0;
        for(int j=0,k;j<a1.size()&&(k=i-a1[j].first+1)>=0;j++)
            t=(t+1ll*a1[j].second*k%mod*f[k])%mod;
        for(int j=1,k;j<a2.size()&&(k=i-a2[j].first)>=0;j++)
            t=(t-1ll*a2[j].second*f[k])%mod;
        f[i]=(0ll+f[i]+t+mod)%mod;
//      cout<<f[i]<<",";
    }
    cout<<f[n]<<endl;
}

T3

原题是正睿 21 省选十连测 day7T2，把 n 从 8 加到 50

按照题意，写出前 n-1 小的长度之和的分布 OGF

F=[t^{n-1}]\prod_{i=0}^{X}\left(\sum_{j=0}^Kt^jx^{ij}\right) i\leq Y$ 时贡献为 $0$，$Y<i\leq L$ 时贡献为 $i-Y$，$i>L$ 时贡献为 $L-Y+1$. 于是我们大概需要算 $\sum_{i\leq s} i\cdot f_i$ 和 $\sum_{i\leq s} f_i$. 后者是 $[x^s]F/(1-x)$，前者是 $[x^s]xF'/(1-x)

现在来考察 F. 注意为了简化形式，下面的一些变量和原问题中的变量并不相同.

首先写出等比数列求和的封闭形式

[t^n]\prod_{i=0}^{X-1}\frac{1-(tx^i)^K}{1-tx^i}

注意分子分母都是有漂亮的形式的，这个乘积可以展开为:

\left(\sum_{i\geq 0}t^i\binom{i+X-1}{i}_x\right)\left(\sum_{i\geq 0}t^{Ki}(-1)^ix^{Ki(i-1)/2}\binom{X}{i}_{x^K}\right)

其中 \dbinom{n}{m}_q 是 q-二项式系数：

\binom{n}{m}_q=\frac{(1-q^n)\cdots(1-q^{n-m+1})}{(1-q^m)\cdots(1-q)}

这个展开式可以这样获得：以分母为例，令

Q(x,t)=\prod_{i=0}^{X-1}\frac{1}{1-tx^i}

注意到

Q(x,tx)=Q(x,t)\frac{1-t}{1-tx^X}

按第二维展开可以获得系数的递推式.

接下来，枚举左右的求和指标 i,j，其应当满足 i+Kj=n. 现在我们要计算两个 q-二项式系数的乘积. 由于 X 很大而 i 很小，我们可以再展开一次:

(1-x^X)\cdots(1-x^{X+i-1})=\sum_{j=0}^ix^{Xj}x^{j(j-1)/2}\binom{i}{j}_x (-1)^ix^{i(i-1)/2}(1-x^X)\cdots(1-x^{X-i+1})=(x^X-1)\cdots(x^X-x^{i-1})=\sum_{j=0}^ix^{X(i-j)}(-1)^jx^{j(j-1)/2}\binom{i}{j}_x

暴力枚举所有的求和指标并对每个 i 计算 x^{Xi} 前面的系数. 显然，每个系数都是一个有理分式，我们可以用线性递推来计算远处系数. 一共要做 O(n) 次长度为 O(n^2) 的线性递推，使用 FFT 则这部分复杂度为 O(n^3\log n\log L). 计算系数时，求和指标的枚举一共花费 O(n^3) 的时间，每次要做长为 O(n^2) 的乘法，使用 FFT 则这部分复杂度为 O(n^5\log n). 事实上可以进一步卷积优化到 O(n^4\log n)，不过不太好写且对常数损失较大.

上面是我场上写的做法. 还有一个更简单也更一般的做法. 直接考虑设

Q(x,t)=\prod_{i=0}^{X-1}\frac{1-(tx^i)^K}{1-tx^i}

由 Q(x,t) 和 Q(x,tx) 的关系得出递推式，把 x^X 看成变元 y，则每次可以在 O(nM(n^2)) 时间内完成转移，总共 O(n^2M(n^2)). 也可以不用 FFT，动态通分即可做到 O(n^5)，不过我猜还是前面快. 线性递推的部分是一样的 O(nM(n^2)\log L).

虽然下面这个做法看起来优秀得多，但实际跑起来差不多（因为瓶颈其实在线性递推）

代码去掉了板子

//sol1
Poly qfac[105][105];
int n,X,Y,K,L;
Z calcall()
{
    Poly a;a.resize(n+1);
    for(int i=0;i<K;i++)a[i]=1;
    Poly g;g.resize(n+1);
    g[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)g[i+1]+=Z(X)*Z(j+1)*a[j+1]*g[i-j];
        for(int j=0;j<i;j++)g[i+1]-=Z(j+1)*g[j+1]*a[i-j];
        g[i+1]*=Z(i+1).inv();
    }
    return g[n];
}
Poly comK(const Poly &a)
{
    Poly ans;ans.resize((a.size()-1)*K+1);
    for(int i=0;i<a.size();i++)
        ans[i*K]=a[i];
    return ans;
}
struct FRAC
{
    Poly fz,fm;
    int u1,u2,v1,v2;
    void clear(){fz=Poly(0),fm=Poly(1),u1=u2=v1=v2=0;}
    void ins(int tu1,int tu2,int tv1,int tv2)
    {
        Poly t0=Poly((tu1+tv1)%2?-1:1)<<(tu1*(tu1-1)/2+tv1*(tv1-1)/2*K);
        if(tu1>tu2)swap(tu1,tu2);
        if(tv1>tv2)swap(tv1,tv2);
        int ru1=max(u1,tu1),ru2=max(u2,tu2);
        int rv1=max(v1,tv1),rv2=max(v2,tv2);
        Poly d=qfac[u1+1][ru1]*qfac[u2+1][ru2]*comK(qfac[v1+1][rv1]*qfac[v2+1][rv2]);
        fm*=d;
        fz*=d;
        u1=ru1,u2=ru2,v1=rv1,v2=rv2;
        fz+=qfac[tu1+1][ru1]*qfac[tu2+1][ru2]*comK(qfac[tv1+1][rv1]*qfac[tv2+1][rv2])*t0;
//      print(fz),print(fm);puts("");
    }
}h[100];
Z calc(int s,int tp)
{
    Z ans=0;
    using namespace Recursive;
    for(int i=0;i<=n&&1ll*i*X<=s;i++)
    {
//      cout<<i<<":"<<endl;
//      print(h[i].fz),print(h[i].fm);
//      puts("");
        if(tp==0)ans+=Liner(h[i].fz,h[i].fm*Poly(1,-1),s-i*X);
        else ans+=Liner(Poly(i*X)*h[i].fz*h[i].fm+((Der(h[i].fz)*h[i].fm-h[i].fz*Der(h[i].fm))<<1),Poly(1,-1)*h[i].fm*h[i].fm,s-i*X);
    }
    return ans;
}
void prework(int n)
{
    for(int l=1;l<=n+1;l++)
    {
        qfac[l][l-1]=Poly(1);
        for(int r=l;r<=n;r++)
        {
            qfac[l][r]=qfac[l][r-1];qfac[l][r].resize(qfac[l][r].size()+r);
            for(int i=qfac[l][r].size()-1;i>=r;i--)
                qfac[l][r][i]-=qfac[l][r][i-r];
        }
    }
    for(int i=0;i<=n;i++)h[i].clear();
    for(int j=0;j*K<=n&&j<=X;j++)
    {
        int i=n-j*K;
        for(int u=0;u<=i;u++)
            for(int v=0;v<=j;v++)
                h[u+(j-v)*K].ins(u,i-u,v,j-v);
    }

}
int main()
{
    freopen("data.txt","r",stdin);
//  freopen("cswa.txt","w",stdout);
    scanf("%d%d%d%d%d",&n,&L,&Y,&X,&K);
    ++X,++K;--n;
    prework(n);
    Z ans=Z(L-Y+1)*calcall();
    ans-=Z(L+1)*calc(L,0);
    ans+=Z(Y)*calc(Y,0);

    ans+=calc(L,1)-calc(Y,1);
    print(ans);puts("");
}
//sol2
Poly qfac[105][105];
int n,X,Y,K,L;
Z calcall()
{
    Poly a;a.resize(n+1);
    for(int i=0;i<K;i++)a[i]=1;
    Poly g;g.resize(n+1);
    g[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)g[i+1]+=Z(X)*Z(j+1)*a[j+1]*g[i-j];
        for(int j=0;j<i;j++)g[i+1]-=Z(j+1)*g[j+1]*a[i-j];
        g[i+1]*=Z(i+1).inv();
    }
    return g[n];
}
Poly f[100][100],df[100];
Z calc(int s,int tp)
{
    Z ans=0;
    using namespace Recursive;
    for(int i=0;i<=n&&1ll*i*X<=s;i++)
    {
//      print(f[n][i]);
        if(tp==0)ans+=Liner(f[n][i],qfac[1][n]*Poly(1,-1),s-i*X);
        else ans+=Liner(df[i],Poly(1,-1)*qfac[1][n]*qfac[1][n],s-i*X);
    }
    return ans;
}
void prework(int n)
{
    for(int l=1;l<=n+1;l++)
    {
        qfac[l][l-1]=Poly(1);
        for(int r=l;r<=n;r++)
        {
            qfac[l][r]=qfac[l][r-1];qfac[l][r].resize(qfac[l][r].size()+r);
            for(int i=qfac[l][r].size()-1;i>=r;i--)
                qfac[l][r][i]-=qfac[l][r][i-r];
        }
    }
    f[0][0]=Poly(1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i-1;j++)
            f[i][j]+=f[i-1][j];
        for(int j=0;j<=i-1;j++)
            f[i][j+1]-=f[i-1][j]<<(i-1);
        if(i>=K)
        {
            for(int j=0;j<=i-K;j++)
                f[i][j+K]+=f[i-K][j]*qfac[i-K+1][i-1];
            for(int j=0;j<=i-K;j++)
                f[i][j]-=f[i-K][j]*qfac[i-K+1][i-1]<<(i-K);
        }
        if(i>=K+1)
        {
            for(int j=0;j<=i-K-1;j++)
                f[i][j+K]-=f[i-K-1][j]*qfac[i-K][i-1];
            for(int j=0;j<=i-K-1;j++)
                f[i][j+1]+=f[i-K-1][j]*qfac[i-K][i-1]<<(i-K-1);
        }
    }
    for(int i=0;i<=n;i++)df[i]=Poly(i*X)*f[n][i]*qfac[1][n]+((Der(f[n][i])*qfac[1][n]-f[n][i]*Der(qfac[1][n]))<<1);
}
int main()
{
    freopen("data.txt","r",stdin);
//  freopen("cswa.txt","w",stdout);
    scanf("%d%d%d%d%d",&n,&L,&Y,&X,&K);
    ++X,++K;--n;
    prework(n);
    Z ans=Z(L-Y+1)*calcall();
    ans-=Z(L+1)*calc(L,0);
//  cout<<calc(L,0)<<endl;
    ans+=Z(Y)*calc(Y,0);
    ans+=calc(L,1)-calc(Y,1);
    print(ans);puts("");
}