2021“MINIEYE杯”中国大学生算法设计超级联赛（7）

终于开补我零作用的场次了。

居然在开学前补完了。

[1001 Fall with Fake Problem]

solution

题面：给出展开字符串，找出字典序不比它小但最小的字符串满足中每个字符的出现次数要么是，要么是给定数字的因数。

做法：因为有字典序最小的条件，那么最终串肯定要是前面一部分和相等，后面的第一个比大这样的串。于是二分这个位置，二分后变成判定性问题，即判断在这个位置前都相等的话，后面能不能满足条件。而由于字典序最小已经转在了二分上，所以这里满足条件就不用字典序最下了，而是要字典序大于。既然要大于，不然取最大。于是我们就想使最大的字符出现次数最多。如果把每个字符与的每个因数的个数差距跑个背包，那背包大小为后面部分就是我们想要的答案。再用这个背包贪心地构造答案，即从大到小选取，大的选尽量多，最后再把这个新的串从大到小排好，比较一下，就处理好二分的判断了。另一方面，知道从哪个位置开始变化后，枚举这个位置的字符，那后面就变成贪心地选取最小的，类似上面的做法一样处理。

背包复杂度是的，二分判断的复杂度就是，后面枚举构造答案的复杂度是，为字符集大小，这似乎不好过。冷静一下，发现背包是判断性的背包，可以 bitset 优化，于是总复杂度就是。

//2021.8.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,k;
    char str[N];
    bitset<N> f[27];
    int a[27],b[27];
    int fac[N],facx;
    inline bool get(const res &len){
        for(res i=1;i<=26;i++){
            f[i].reset();
            for(res j=1;j<=facx;j++){
                if(fac[j]<a[i])break;
                f[i]|=(f[i-1]<<(fac[j]-a[i]));
            }
        }
        if(!f[26][len])return 0;
        res now=len;
        for(res i=26;i;i--){
            for(res j=1;j<=facx;j++){
                res r=fac[j]-a[i];
                if(0<=r&&r<=now&&f[i-1][now-r]){now-=r,b[i]=r;break;}
            }
        }
        return 1;
    }
    inline bool ck(const res &lim){
        for(res i=1;i<=26;i++)a[i]=0;
        for(res i=1;i<=lim;i++)a[str[i]-'a'+1]++;
        for(res i=1;i<=26;i++)if(a[i]>k)return 0;
        if(!get(n-lim))return 0;
        res now=26;
        for(res i=lim+1;i<=n;i++){
            while(!b[now]&&now)now--;
            if(now<str[i]-'a'+1)return 0;
            if(now>str[i]-'a'+1)return 1;
            b[now]--;
        }
        return 1;
    }
    inline void MAIN(){
        f[0][0]=1;
        res Case=read();
        while(Case--){
            n=read(),k=read(),scanf("%s",str+1),facx=0;
            res mx=0;
            for(res i=1;i<=26;i++)a[i]=0;
            for(res i=1;i<=n;i++)a[str[i]-'a'+1]++;
            for(res i=k;i;i--)if(k%i==0)fac[++facx]=i;
            fac[++facx]=0;
            res l=0,r=n,ret=-1;
            while(l<=r){
                res mid=(l+r)>>1;
                if(ck(mid))l=mid+1,ret=mid;
                else r=mid-1;
            }
            if(ret==-1){puts("-1");continue;}
            for(res i=1;i<=ret;i++)putchar(str[i]);
            for(res i=1;i<=26;i++)a[i]=0;
            for(res i=1;i<=ret;i++)a['z'-str[i]+1]++;
            str[n+1]='z';
            for(res i=str[ret+1]+1;i<='z';i++){
                a['z'-i+1]++;
                if(!get(n-ret-1)){a['z'-i+1]--;continue;}
                putchar(i);
                for(res j=26;j;j--)while(b[j]--)putchar('z'-j+1);
                break;
            }
            puts("");
        }
    }
}

[1002 Fall with Soldiers]

solution

题面：一个序列有，你每次可以选择一个不在最左右的将其相邻的两个数删掉，当不能操作时序列只剩则是你赢，可以是或，由你决定。现有次单点修改，问填的方案数使你存在一种胜利方式。保证序列长度为奇数。

做法：容易得出最后必胜的充要条件：

$a_i=a_i=1\ \And\ i\leq \frac{n+1}{2}\leq j\leq i+\frac{n-1}{2}$

而此时的看似很多，实际上我们只用考虑最靠中间的，贪心来看这样一定是不劣的。

于是我们分类讨论下。

，其中代表都是。

这种情况下的答案显然看那两个是否合法，合法的话答案就是，代表个数，不合法就是。
。

这种情况下我们找出右边的那个对应的最小的，即。然后从左边靠中第一个向移动，碰到就停止。设总的为个，停止前碰到的数量为，那答案就是 $碰到$ 。左边有同理。
。

这种情况复杂一点。我们对于右边的每一个求出它最小的，即，记录到中有几个是在出现前的，设为。那答案就是

$第二种情况向左碰到$ ，其中表示是第几个。

看似好复杂，冷静一下发现都是单调的，再冷静一下发现这些信息都是容易用线段树维护的。总时间复杂度。当然也存在其他讨论的方式，不过没什么太大影响。

代码实现可能和上述讲述不符。

//2021.8.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,q;
    char str[N];
    int pw[N];
    set<int> S1,S2;
    int tr[N<<2],laz[N<<2],vis[N<<2];
    int tot;
    inline void change(const res &rt,const res &v){
        laz[rt]=mul(laz[rt],v),tr[rt]=mul(tr[rt],v);
    }
    inline void pushdown(const res &rt){
        if(laz[rt]==1)return;
        change(rt<<1,laz[rt]),change(rt<<1|1,laz[rt]),laz[rt]=1;
    }
    inline void pushup(const res &rt){
        tr[rt]=Add(vis[rt<<1]?tr[rt<<1]:0,vis[rt<<1|1]?tr[rt<<1|1]:0);
    }
    void build(res rt,res l,res r){
        laz[rt]=vis[rt]=1;
        if(l==r){tr[rt]=1,vis[rt]=str[l]=='?';return;}
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
    }
    void modify_rev(res rt,res l,res r,const res &p){
        if(l==r){vis[rt]^=1;return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(p<=mid)modify_rev(rt<<1,l,mid,p);
        else modify_rev(rt<<1|1,mid+1,r,p);
        pushup(rt);
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &v){
        if(L<=l&&r<=R){change(rt,v);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,v);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,v);
        pushup(rt);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(!vis[rt])return 0;
        if(L<=l&&r<=R)return tr[rt];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)add(ret,query(rt<<1|1,mid+1,r,L,R));
        pushup(rt);
        return ret;
    }
    int mid;
    inline int query(res p){
        if(!p)p++;
        res rt=1,l=1,r=mid-1;
        while(l<r){
            res m=(l+r)>>1;
            pushdown(rt);
            if(p<=m)rt=rt<<1,r=m;
            else rt=rt<<1|1,l=m+1;
        }
        return tr[rt];
    }
    inline int calc(){
        res mx,mn;
        if(str[mid]=='1')return pw[tot];
        if(S1.empty())mx=0;
        else mx=*--S1.end();
        if(S2.empty())mn=n;
        else mn=*S2.begin();
        if(mn-mx<mid)return pw[tot];
        return Add(pw[tot],kcz-Add(query(mx),query(1,1,mid-1,mx+1,mn-mid)));
    }
    char t[3];
    inline void MAIN(){
        res INV2=qpow(2);
        pw[0]=1;
        for(res i=1;i<=N-10;i++)pw[i]=Add(pw[i-1],pw[i-1]);
        res Case=read();
        while(Case--){
            n=read(),q=read(),scanf("%s",str+1),set<int>().swap(S1),set<int>().swap(S2),mid=(n+1)>>1,tot=0;
            for(res i=1;i<mid;i++)if(str[i]=='1')S1.insert(i);
            for(res i=mid+1;i<=n;i++)if(str[i]=='1')S2.insert(i);
            for(res i=1;i<=n;i++)tot+=(str[i]=='?');
            build(1,1,mid-1);
            for(res i=mid+1;i<=n;i++)if(str[i]=='?')modify(1,1,mid-1,1,i-mid,2);
            for(res i=1;i<mid-1;i++)if(str[i]=='?')modify(1,1,mid-1,i+1,mid-1,2);
            printf("%d\n",calc());
            while(q--){
                res i=read();
                scanf("%s",t+1);
                if(str[i]!=t[1]){
                    tot+=(t[1]=='?')-(str[i]=='?');
                    if(i==mid);
                    else {
                        if(str[i]=='1'){
                            if(i<mid)S1.erase(i);
                            else S2.erase(i);
                        }
                        if(t[1]=='1'){
                            if(i<mid)S1.insert(i);
                            else S2.insert(i);
                        }
                        if(str[i]!='?'&&t[1]!='?');
                        else {
                        if(i<mid){
                            modify_rev(1,1,mid-1,i);
                            if(i<mid-1)modify(1,1,mid-1,i+1,mid-1,(t[1]=='?'?2:INV2));
                        }
                        else modify(1,1,mid-1,1,i-mid,(t[1]=='?'?2:INV2));
                        }
                    }
                    str[i]=t[1];
                }
                printf("%d\n",calc());
            }
        }
    }
}

[1003 Fall with Trees]

solution

题面：我们首先规定树中所有具有相同深度的节点在平面上也具有相同的坐标。将相同深度的节点定义为相同层次的节点，那么完美二叉树有四个属性。

满二叉树。
相邻两层节点的坐标差为常数。
同一层次上两个相邻节点的坐标差为常数。
每个节点的坐标是其子节点坐标的平均值。
我已经画出了这个二叉树的根节点和它的左右两个子节点。现在打算画出总共个层次，他想知道这个完美二叉树的所有节点的凸包的面积是多少。

做法：。。。一心想着推导每一层最左端点的值，然后就吐血了。

实际上直接推导两层之间的深度关系，就会发现是个等比数列了。而最终答案就是所有梯形面积之和，发现还是个等比数列求和。所以就了。

//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int k;
    LL xa,ya,xb,yb,xc,yc,dy,dx,ans,tmp;
    inline void MAIN(){
        res Case=read();
        while(Case--){
            scanf("%d%lld%lld%lld%lld%lld%lld",&k,&xa,&ya,&xb,&yb,&xc,&yc),k--;
            dy=abs(ya-yb),dx=abs(xa-xb);
            ans=dx*dy*(4*k-6)*1000,tmp=dx*dy*6*1000;
            res flag=1;
            while(k--&&(tmp||flag))flag=tmp&1,tmp/=2;
            ans+=tmp+flag;
            printf("%lld.%03lld\n",ans/1000,ans%1000);
        }
    }
}

[1004 Link with Balls]

solution

题面：个桶，第个桶中可以取出的倍数个球，第个桶最多取出个球，问取出个球的方案数。

做法：写出，即求

$[x^m]\prod_{i=1}^n\frac{1-x^{i+1}}{(1-x^i)(1-x)}\\\\ =[x^m]\frac{1-x^{n+1}}{(1-x)^{n+1}}$

想怎么做就怎么做，因为这题比较小，那就隔板法做。当然因为这是分式，所以显然可以线性递推做到单个，这里不再赘述。

//2021.8.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    int n,m;
    int fac[N],inv[N];
    inline int C(const res &x,const res &y){
        return mul(fac[x],mul(inv[y],inv[x-y]));
    }
    inline void MAIN(){
        fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(res i=2;i<=N-10;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=N-10;i++)inv[i]=mul(inv[i-1],inv[i]);
        res Case=read();
        while(Case--){
            n=read(),m=read();
            res r=C(m+n,n);
            if(m-n-1>=0)add(r,kcz-C(m-1,n));
            printf("%d\n",r);
        }
    }
}

[1005 Link with EQ]

solution

题面：有张椅子排成一列，第一个人随机做，接下来的人做的位置和已经被坐位置的距离的最小值必须保证最大，若有多个最大的位置，随机选择一个。不能有人相邻。问期望坐下来的人数。

做法：第一个人坐下来后，肯定会选择两边的端点（如果可以）。然后整个就被拆成两段，每段的两段都有人坐了。发现之后每个人肯定会坐中间的位置，于是总的人数一定是唯一的。因此可以先求出表示两端都有人坐，中间还有个位置，最终能坐下来的人数。转移就是把再拆成两段即可。然后枚举第一个人做的位置，发现枚举 + 求和的式子就是在求的前缀和，于是就可以了。我懒得再写一遍式子了。

代码我偷懒直接了，不过无所谓。

//2021.8.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int f[N],g[N],h[N];
    inline void MAIN(){
        f[1]=f[2]=0;
        for(res i=3;i<=N-10;i++){
            if(i&1){
                res d=i>>1;
                f[i]=Add(Add(f[d],f[d]),1);
            }
            else {
                res d=i>>1;
                f[i]=Add(Add(f[d],f[d-1]),1);
            }
        }
        for(res i=3;i<=N-10;i++)g[i]=Add(g[i-1],f[i]);
        h[1]=1;
        for(res i=2;i<=N-10;i++)h[i]=Add(Add(g[i-2],g[i-2]),3*i-4),h[i]=mul(h[i],qpow(i));
        res Case=read();
        while(Case--){
            printf("%d\n",h[read()]);
        }
    }
}

[1006 Link with Grenade]

solution

题面：你在一个地方按角度随机朝一方面扔炸弹，炸弹的初始速度为，它在秒后会爆炸，你在距离爆炸点以内会直接死亡，问你不死的概率。

做法：先说下我看似错误但实则正确的做法。

我开始下意识认为随机一个角度可以等价于随机一个旋转角度再随机一个二维的抛物角度，这个旋转角度正好决定了抛物线在哪个面上。然后我觉得旋转角度是随机的，那每个面都是一样的，然后转成二维平面，看抛物线落点离原点的距离。接着我算出一个式子，大致是这样的东西，为抛物角度。于是我冷静一下，如果抛物角度是随机的，那答案不就是了吗，这怎么取模啊！这时机智（弱智）的我猜想题意是按随机的，所以就直接写出来交了一发，然后过了。。。

看完题解后觉得有点奇异，它明明确实是按角度随机的啊，那我不是完全理解错误？确实如此。原因很简单，立体角是一个独立的角，而不是所谓的旋转角度随机完再抛物角度随机的产物，这点上我的理解是完全错误的。但是，一旦后面按随机，它确实是对的。这是因为立体角满足。其中，熟知立体角的同学就会发现，这里的恰好是所谓的旋转角度，而虽然不是所谓的抛物角度，但却是所谓的抛物角度。于是我们改写立体角的公式，即，于是随机一个，它确实等价于随机一个再随机一个，而巧的是，所以凑巧我就炸胡对了。。。

官方做法是直接考虑立体角，直接求抛物面是不容易的，所以变成人在向上动，炸弹稳定地冲。那题意就被转化成求两个球体的交中一个球体的表面积大小，这可以积分算出，于是就做出来了。

炸胡真爽。

//2021.8.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    inline void MAIN(){
        res Case=read();
        while(Case--){
            res t=read(),v=read(),r=read();
            RG LL p=4ll*v*v*t*t+100ll*t*t*t*t-4ll*r*r+40ll*v*t*t*t;
            if(p<=0)puts("0");
            else {
                res q=80*v*t*t*t;
                if(p>=q)puts("1");
                else printf("%d\n",mul(int(p%kcz),qpow(q)));
            }
        }
    }
}

[1007 Link with Limit]

solution

题面：给出的个点值，即，保证值域小于等于大于等于，定义。问

$g(x)=\lim_{n\to \infty}\frac{1}{n} \sum_{i=1}^n f_i(x)$

对每个是否相等？

做法：由于求的是函数序列的级数，所以常数部分可以去除。若构成一条边，则级数中肯定存在一个循环，所以就等价于找循环。由于每一条边只有一个出度，所以暴力。判断两个循环是否相等就等价于求两者循环长度的即可。时间复杂度。

//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,f[N];
    int vis[N],tim;
    int st[N],top;
    LL s;
    int sm;
    Pair a[N],b[N];
    int ax;
    void dfs(res x){
        if(vis[x]==tim)return;
        if(vis[x]){s=b[x].fi,sm=b[x].se;return;}
        st[++top]=x,vis[x]=tim,s+=x,sm++,dfs(f[x]);
    }
    inline void solve(){
        for(res i=1;i<ax;i++)if(1ll*a[i].fi*a[i+1].se!=1ll*a[i].se*a[i+1].fi){puts("NO");return;}
        puts("YES");
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),ax=tim=0;
            for(res i=1;i<=n;i++)f[i]=read(),vis[i]=0;
            for(res i=1;i<=n;i++)if(!vis[i]){
                s=sm=top=0,tim++,dfs(i),a[++ax]=mp(s,sm);
                for(res j=1;j<=top;j++)b[st[j]]=mp(s,sm);
            }
            solve();
        }
    }
}

[1008 Smzzl with Greedy Snake]

solution

题面：二维平面上有个食物，一个贪吃蛇初始在，逆时针或顺时针转向都耗费的时间，前进一个单位耗费的时间。个食物按序出现，吃完一个食物下一个食物才会出现。保证个相邻的坐标互不相同。问最短时间的操作序列。可以证明是唯一的。

做法：四种分十六类讨论即可，时间复杂度。

//2021.8.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    char str[2000010];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            res x=read(),y=read(),d=read(),n=read();
            res sx=0;
            for(res i=1;i<=n;i++){
                res X=read(),Y=read();
                res o=abs(X-x),p=abs(Y-y);
                if(X>x){
                    if(Y>y){
                        if(d==0){
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=1;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else if(d==1){
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=0;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else if(d==2){
                            str[++sx]=('u');
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=0;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else {
                            str[++sx]=('c');
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=1;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                    }
                    else {
                        if(d==0){
                            str[++sx]=('c');
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=2;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else if(d==1){
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=2;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else if(d==2){
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=1;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else {
                            str[++sx]=('u');
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=1;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                    }
                }
                else {
                    if(Y>y){
                        if(d==0){
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=3;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else if(d==1){
                            str[++sx]=('u');
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=3;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else if(d==2){
                            str[++sx]=('c');
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=0;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else {
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=0;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                    }
                    else {
                        if(d==0){
                            str[++sx]=('u');
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=2;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                        else if(d==1){
                            str[++sx]=('c');
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=3;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else if(d==2){
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                            str[++sx]=('c'),d=3;
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                        }
                        else {
                            for(res j=1;j<=o;j++)str[++sx]=('f');
                            str[++sx]=('u'),d=2;
                            for(res j=1;j<=p;j++)str[++sx]=('f');
                        }
                    }
                }
                x=X,y=Y;
            }
            for(res i=1;i<=sx;i++)printf("%c",str[i]);puts("");
        }
    }
}

[1009 Smzzl with Safe Zone]

solution

题面：求外凸包上的点到内凸包上的点最小距离的最大值。

做法：大胆猜测一定是外凸包上的点才是答案要求的点，证明分两类讨论。

感受一下，肯定是外凸包上的点到它对面的点和边的距离是答案，而随着外凸包上的点按顺时针选过来时，对应的点和边也是按序选过来的，于是利用这种类似的单调性就可以了。

//2021.8.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int m,n;
    Pair a[N],b[N];
    inline Pair operator - (const RG Pair &x,const RG Pair &y){
        return mp(x.fi-y.fi,x.se-y.se);
    }
    inline LL len(const RG Pair &x){
        return 1ll*x.fi*x.fi+1ll*x.se*x.se;
    }
    inline LL operator * (const RG Pair &x,const RG Pair &y){
        return 1ll*x.fi*y.fi+1ll*x.se*y.se;
    }
    inline LL operator ^ (const RG Pair &x,const RG Pair &y){
        return 1ll*x.fi*y.se-1ll*x.se*y.fi;
    }
    struct Ans{
        int x;
        long db y;
        Ans() {}
        Ans(res x,RG long db y):x(x),y(y) {}
        Ans(RG LL a):x(int(a%kcz)),y(sqrtl(a)) {}
        inline bool operator < (const RG Ans &A) const {
            return y<A.y;
        }
    };
    inline int get(const res &o){
        return o<=m?o:o-m;
    }
    inline Ans calc(const RG Pair &x,const RG Pair &y,const RG Pair &z){
        RG LL a=abs((x^y)+(y^z)+(z^x)),b=len(y-z);
        res pa=int(a%kcz),pb=int(b%kcz);
        pa=mul(pa,pa);
        return Ans(mul(pa,qpow(pb)),a/sqrtl(b));
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            m=read();
            for(res i=1;i<=m;i++){
                res x=read(),y=read();
                a[i]=mp(x,y);
            }
            n=read();
            for(res i=1;i<=n;i++){
                res x=read(),y=read();
                b[i]=mp(x,y);
            }
            RG Ans ans=Ans(0,0);
            res k=1;
            for(res i=2;i<=m;i++)if(len(a[k]-b[1])>len(a[i]-b[1]))k=i;
            for(res i=1;i<=n;i++){
                while(len(a[k]-b[i])>len(a[get(k+1)]-b[i]))k=get(k+1);
                if(((b[i]-a[k])*(a[get(k+1)]-a[k]))>=0)ans=max(ans,calc(b[i],a[k],a[get(k+1)]));
                else if(((b[i]-a[k])*(a[get(k+m-1)]-a[k]))>=0)ans=max(ans,calc(b[i],a[k],a[get(k+m-1)]));
                else ans=max(ans,Ans(len(b[i]-a[k])));
            }
            printf("%d\n",ans.x);
        }
    }
}

[1010 Smzzl with Tropical Taste]

solution

题面：游泳池里有升的冰红茶，开始时升，主人倒冰红茶的速度是升/秒，男孩喝冰红茶的速度是升/秒，喝完为止。

给定，求解：对于任意，是否存在一个，对于任意，男孩在秒后喝了超过升的冰红茶。

做法：稍作推导，即第时刻的红茶量应该是，发现这东西若存在则一定发散，存在条件是，于是就结束了。

//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res Case=read();
        while(Case--){
            db p,q;
            cin>>p>>q;
            puts(q>=p?"N0 M0R3 BL4CK 1CE TEA!":"ENJ0Y YOURS3LF!");
        }
    }
}

[1011 Yiwen with Formula]

solution

题面：求所有子序列的和的积。

做法：求积的和是 djq 鸽鸽放在 loj 上的题，这里不赘述。

容易去考虑，于是答案等于

$\begin{align*} &\prod_{n\geq 0} n^{[x^n] F(x)}(不妨设 0^0=0)\\ &其中 F(x)=\prod_{i=1}^n \frac{1}{1-x^{a_i}} &\end{align*}$

所以直接取出就求出这道题了。看似已经结束了，但恶心的是的系数是在答案的指数上的，这意味着的系数要模，于是就要了。于是要么取再回去做到，要么写个启发式合并迅速跑路。

蛤，你问我写了啥？我啥都不想写，贺了队友代码就直接跑路喽！

多项式还是让我口胡比较好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int maxlogn=17;
const int maxn=(1<<maxlogn)|1;
const int kcz=998244353;
const db tau=2*acosl(-1);
int n,rev[maxn],w0,sz[maxn];
ll G[2][24],ans;
vector<int> f[maxn];
struct cmp
{
    inline bool operator()(const int &x,const int &y)
    {
        return sz[x]>sz[y];
    }
};
priority_queue<int,vector<int>,cmp> que;
struct comp
{
    db a,b;
    comp(db a=0,db b=0):a(a),b(b) {}
    inline comp operator +(const comp &x) const { return comp(a+x.a,b+x.b); }
    inline comp operator -(const comp &x) const { return comp(a-x.a,b-x.b); }
    inline comp operator *(const comp &x) const { return comp(a*x.a-b*x.b,a*x.b+b*x.a); }
}w[maxn];
inline void calcrev(int logn)
{
    int i;
    for(rev[0]=0,i=1;i<(1<<logn);i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(logn-1));
}
inline void init()
{
    int i;
    for(i=0;i<=(1<<maxlogn);i++)
        w[i]=comp(cosl(i*tau/(1<<maxlogn)),sinl(i*tau/(1<<maxlogn)));
}
inline void DFT(comp *a,int logn,bool flag)
{
    int i,j,k,mid;
    comp x,y;
    for(i=0;i<(1<<logn);i++)
        if(rev[i]<i)
            swap(a[rev[i]],a[i]);
    for(i=1;i<=logn;i++)
        for(mid=1<<(i-1),j=0;j<(1<<logn);j+=1<<i)
            for(k=0;k<mid;k++)
            {
                x=a[j|k],y=a[j|k|mid]*w[flag?(1<<maxlogn)-(k<<(maxlogn-i)):(k<<(maxlogn-i))];
                a[j|k]=x+y,a[j|k|mid]=x-y;
            }
}
comp a[maxn],b[maxn],c[maxn],d[maxn];
int h[maxn];
inline long long rnd(db x) { return (long long)(x+.5); }
inline void MTT(const vector<int> &f,const vector<int> &g,int logn)
{
    int i;
    const int kcz=998244352;
    comp x,y,z;
    calcrev(logn);
    for(i=0;i<(1<<logn);i++) a[i]=comp(f[i]>>16),b[i]=comp(f[i]&0xffff),c[i]=comp(g[i]>>16),d[i]=comp(g[i]&0xffff);
    DFT(a,logn,0),DFT(b,logn,0),DFT(c,logn,0),DFT(d,logn,0);
    for(i=0;i<(1<<logn);i++)
        x=a[i]*c[i],y=a[i]*d[i]+b[i]*c[i],z=b[i]*d[i],a[i]=x,b[i]=y,c[i]=z;
    DFT(a,logn,1),DFT(b,logn,1),DFT(c,logn,1);
    for(i=0;i<(1<<logn);i++) a[i].a/=1<<logn,b[i].a/=1<<logn,c[i].a/=1<<logn;
    for(i=0;i<(1<<logn);i++) h[i]=(((rnd(a[i].a)%kcz)<<32)+((rnd(b[i].a)%kcz)<<16)+rnd(c[i].a))%kcz;
}
inline void mult(int a,int b)
{
    int logn,i;
    for(logn=0;(1<<logn)<sz[a]+sz[b]-1;logn++);
    calcrev(logn);
    while(f[a].size()<(1<<logn)) f[a].push_back(0);
    while(f[b].size()<(1<<logn)) f[b].push_back(0);
    MTT(f[a],f[b],logn);
    for(i=0;i<(1<<logn);i++) f[a][i]=h[i];
    sz[a]+=sz[b]-1;
}
inline ll qpow(ll a,ll k)
{
    ll res=1;
    while(k)
    {
        if(k&1) (res*=a)%=kcz;
        if(k>>=1) (a*=a)%=kcz;
    }
    return res;
}
int main()
{
    int T,n,i,x,y;
    ll ans;
    bool flag;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n),flag=false;
        while(!que.empty()) que.pop();
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            if(!x) flag=true;
            else
            {
                vector<int>().swap(f[i]),f[i].push_back(1);
                while(--x) f[i].push_back(0);
                f[i].push_back(1);
                sz[i]=f[i].size();
            }
            que.push(i);
        }
        if(flag) { printf("0\n"); continue; }
        while(x=que.top(),que.pop(),!que.empty())
        {
            y=que.top(),que.pop();
            mult(x,y);
            que.push(x);
        }
        ans=1;
        for(i=1;i<sz[x];i++)
            (ans*=qpow(i,f[x][i]))%=kcz;
        printf("%lld\n",ans);
    }
    return 0;
}

[1012 Yiwen with Sqc]

solution

题面：表示中的出现次数。求。

做法：直接拆成前缀和即可，即

$\begin{align*} &(\mathrm{sqc(s,1,j,c)}-\mathrm{sqc(s,1,i-1,c)})^2\\ &=\mathrm{sqc(s,1,j,c)}^2+\mathrm{sqc(s,1,i-1,c)}^2-2\mathrm{sqc(s,1,i-1,c)}\mathrm{sqc(s,1,j,c)}\\ &\sum \mathrm{sqc(s,1,j,c)}^2+\mathrm{sqc(s,1,i-1,c)}^2-2\mathrm{sqc(s,1,i-1,c)}\mathrm{sqc(s,1,j,c)}\\ &=\sum_{i=1}^n\mathrm{sqc(s,1,i,c)}^2n-((\sum_{i=1}^n \mathrm{sqc(s,1,i,c)})^2-\sum_{i=1}^{n} \mathrm{sqc(s,1,i,c)}^2) &\end{align*}$

于是就是了。

//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    char str[N];
    int sqc[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            scanf("%s",str+1);
            res n=int(strlen(str+1));
            res ans=0;
            for(res c=0;c<26;c++){
                for(res i=1;i<=n;i++)sqc[i]=sqc[i-1]+(str[i]-'a'==c);
                res s=0,t=0;
                for(res i=1;i<=n;i++)add(s,sqc[i]),add(t,mul(sqc[i],sqc[i]));
                add(ans,Add(mul(t,n+1),kcz-mul(s,s)));
            }
            printf("%d\n",ans);
        }
    }
}