2024 9月第五周杂题

Lacrymabre · 2024-09-28 15:15:13 · 休闲·娱乐

ABC371g

题意：给两个排列 a,p ，可以执行任意多次操作，每次操作会使得 a_{p_i}\to a_{i} 同时发生。求 a 所能到达的最小序。

sol：考虑排列的轮换分解一定不交，那么可以拆成若干个置换环。

因为最小序的需求，所以应该贪心的从前面的位开始取得。我们希望在 x 次操作之后，所有置换都取得最小序。

最好可以朴素的求出，但是这是不太可能的，因为前面的 x 已经对后面的产生了要求。

将相前位应该是 a_j 的情况，我们需要 x\equiv pos_j \mod M ，其中 M 为当前位置所在的环的大小。

可见最终的答案 ans 应该是前面所有的 x\equiv pos\mod M 的同余方程联立的解 x 。

对环上相对位置为 pos_j 的数字置换到当前位置，需要 pos_j+kM 次置换，反之可推。

假如我们得到了最终的 ans 那么最终的排列可以 O(n) 得出，这是非常容易的。

每个 x 可能会产生冲突，冲突时产生一个新的同余方程添加到组里面。否则相当于当前方程可以与前面的方程组合并，无需新增方程。

重复新增同余方程和合并同余方程的过程，解最终的同余方程组，可以得到最终答案。

上述过程需要使用高精度求解 lcm ，代码非常傻逼。

代码能力有限，也想不出不用高精度的方法。故只有思路，代码搁置。

bzoj3284

有一个有 m 个正整数的集合 G 和一个正整数 s (m<S,1\notin G) 。一棵树是合法的当且仅当每个非叶子节点的孩子数量都在集合 G 内。求对于 [1,n] 中的每个 s ，求有多少棵本质不同的树含有 s 个节点。孩子之间有顺序，n\leq10^5。

sol：

设 G 的 OGF 为 g ，那么 g(x)=\sum_{[i\in G]}x^i 。

设答案的 OGF 为 f 。

根据题意，我们可以得到：

根据多项式复合的定义：

为什么是 [x^i]g(i)\times f(x)^i 呢？

对于当前节点，考虑他的儿子数量，应该要有 w 个儿子，意味着有 w 个子树。

多项式复合逆即可求解。

2022sccpc E

求：

sol：

质数相关积性函数问题，考虑 min_25 筛方法。

考虑到三个元难以处理，用套路合并其中两个，变成两个元。

考虑枚举的上界，可以容易得到分割方法。

变成两个元之后，考虑拆开 f 。

那么 (a+b)^3=a^3+3ba^2+3b^2a+b^3 。这样每一个单项式都是可以计算的了。

对于 g 的计算方法不用改变。

考虑原来算 s 的部分，不用求合数贡献，暴力跳块是可以的。

每部分分别计算就可以了。

min_25 的方法就是把原来难以计算的函数拆成若干个可以被处理的单项式。只需要堆砌 g 就可以分解问题了。

特别注意，s 部分计算时，千万不能对 for 上面的判断取模，因为那是边界判断；for 的条件之间要用 && 连接，因为如果用逗号那么整一个条件的值是逗号运算的右值。

void getg(){
    ll T=sqrt(n+0.5);
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        v[++m]=n/l;
        if(v[m]<=N) id1[v[m]]=m;
        else id2[n/v[m]]=m;
        g0[m]=(v[m]-1ll+mod)%mod;
        g1[m]=(qz1(v[m])-1ll+mod)%mod;
        g2[m]=(qz2(v[m])-1ll+mod)%mod;
        g3[m]=(qz3(v[m])-1ll+mod)%mod;
    }
    for(ll j=1;j<=cnt;j++){
        for(ll i=1;i<=m&&p[j]<=v[i]/p[j];i++){
            ll k=get(v[i]/p[j]);
            g0[i]=(g0[i]-(g0[k]-sum0[j-1]+mod)%mod+mod)%mod;g0[i]=(g0[i]+mod)%mod;
            g1[i]=(g1[i]-p[j]*(g1[k]-sum1[j-1]+mod)%mod+mod)%mod;g1[i]=(g1[i]+mod)%mod;
            g2[i]=(g2[i]-sq(p[j])*(g2[k]-sum2[j-1]+mod)%mod+mod)%mod;g2[i]=(g2[i]+mod)%mod;
            g3[i]=(g3[i]-fr(p[j])*(g3[k]-sum3[j-1]+mod)%mod+mod)%mod;g3[i]=(g3[i]+mod)%mod;
        }
    }
    //cout<<"done\n";
}

ll S(ll x,ll y){
    /*if(p[y]>x) return 0;
    ll res=((g2[get(x)]-g1[get(x)]+mod)%mod-(sum2[y]-sum1[y]+mod)%mod+mod)%mod;//g(n);
    //  cout<<"S("<<x<<","<<y<<") = counting"<<" "<<"shit\n";
    for(ll i=y+1;i<=cnt&&p[i]<=x/p[i];i++){
        ll P=p[i];
        for(ll e=1;P<=x;e++,P*=p[i]){//p^e
            res=(res+F(P)*(S(x/P,i)+(e!=1))%mod)%mod;
        }
    }
    //  cout<<"S("<<x<<","<<y<<") = "<<res<<" "<<"shit\n";
    return res;*/
    ll res=0;
    for(int i=1;i<=cnt&&p[i]<=n;i++){
        for(int j=i+1;p[j]*p[j]*p[i]<=n&&j<=cnt;j++){
            // f = (a+b)^3
            // f = (1)b^3 + (3a)b^2 + (3a^2)b + (1)a^3
            ll a = p[i]+p[j],b=n/(p[i]*p[j]);// times up \leq n
            ll sqa=sq(a),fra=fr(a);
            ll pos = get(b);

            res+=fra*((g0[pos]-sum0[j]+mod)%mod)%mod,res%=mod;
            res+=sqa*3%mod*((g1[pos]-sum1[j]+mod)%mod)%mod,res%=mod;
            res+=a*3%mod*((g2[pos]-sum2[j]+mod)%mod)%mod,res%=mod;
            res+=(g3[pos]-sum3[j]+mod)%mod,res%=mod;
        }
    }
    return res;
}

CF2019D

现在有 n 个点连成一排，你每秒可以选择已经被侵占的点相邻的一个点，并且侵占他。在 t=1 时刻你可以侵占任意一个点作为起始点。每个点都有一个限制 a_i ，表示你必须在 a_i 时刻之前侵占这个点。问有多少个起始点能够满足所有限制，当你足够聪明。 n\leq2·10^5

sol:

最朴素的方法是考虑暴力地判断某个位置 pos 是否合法，然后线性统计答案。

贪心的看，为了验证位置 pos 是否合法，应该先侵占掉 [1,pos) 的前缀最小值，(pos,n] 的后缀最小值。然后侵占第二值，第三值……

如果一个位置合法，那么一定可以这样侵占掉所有点。

每次侵占之后，都相当于 可以看作起始点的点的左右边界 扩展到了前后缀最值点。然后化为了子问题。这个是顺序处理的。

能够点完某一个最值的点当且仅当两边需要侵占的点围成的极大区间长度比 当前时间 与 前后缀最值 的差 要小。

进一步的考虑，一个时间 t 想要被侵占，意味着包含 t 的极大区间要被侵占。直接考虑对于 [1,n] 的每一个 t ，能否存在情况都被满足即可。如果侵占前 t 个时间代表的所有点所需的区间长度比 t 还要大，那就总存在位置无法侵占，答案是 0 。

否则回到之前的问题，某个点 i 能被侵占，说明有侵占点位于 U(i,a_i) 中。联立所有方程，得到一个区间，里面就是合法的起始点。

想到这里，我们发现不再需要暴力的算法了。

输出区间长度即可。

void solve(){
    n=read();for(int i=1;i<=n;i++) a[i]=read();
    for(int i=0;i<=n;i++) xp[i]=0,ip[i]=n;
    for(ll i=1;i<=n;i++) xp[a[i]]=max(xp[a[i]],i),ip[a[i]]=min(ip[a[i]],i);
    for(int t=1;t<=n;t++){
        xp[t]=max(xp[t],xp[t-1]);ip[t]=min(ip[t],ip[t-1]);
        if(xp[t]-ip[t]>=t){puts("0");return;}
    }
    ll l=1,r=n;for(int i=1;i<=n;i++) l=max(l,i-a[i]+1),r=min(r,i+a[i]-1);
    cout<<(r-l+1)<<"\n";
}