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

希望能补完。

补完啦！

[1001 Mod, Or and Everything]

solution

题面：求 。

做法：打个表就能发现答案是比 小但最接近 的 的幂次减一（ 除外）。

证明也很简单，假设 的最高位为 ，考虑 ，此时 一定是连续的，而一共有 个数，这是大于等于 的，因此后 位一定为 。而若答案的第 位为 的话，则要求 ​，这显然是错误的。所以证毕了。

时间复杂度 ​。

//2021.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res T=read();
        while(T--){
            RG LL n=Read();
            if(n==1)puts("0");
            else printf("%lld\n",(long long)(powl(2ll,int(log2(n-1))))-1);
        }
    }
}

[1002 Rocket land]

solution

题面：每次投射一个炸弹，爆炸范围是一个圆心为 ​，半径为 ，价值为 ​，若一个之前的炸弹在爆炸范围内，就会产生那个炸弹的贡献。求每个炸弹产生的贡献。保证数据随机。

做法：直接暴力上个 KDT，每次插入的那种，就赢了。复杂度？

//2021.7.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n;
    int D;
    struct P{
        int x[2],val;
        inline bool operator < (const P &b) const {
            return x[D]<b.x[D];
        }
    }a[N];
    inline P init(const res &X,const res &Y,const res &v){
        RG P b;
        b.x[0]=X,b.x[1]=Y,b.val=v;
        return b;
    }
    struct KDT{
#define alph (0.75)
        struct KD{
            int son[2],mx[2],mn[2],sz;
            LL sum;
            P point;
            inline void init(const RG P &b){
                point=b,son[0]=son[1]=0,mx[0]=mn[0]=b.x[0],mx[1]=mn[1]=b.x[1],sum=b.val,sz=1;
            }
        }tr[N];
        int tot;
        int st[N],top;
        inline int newnode(){
            return top?st[top--]:++tot;
        }
        inline void pushup(res rt){
            res ls=tr[rt].son[0],rs=tr[rt].son[1];
            tr[rt].sum=tr[ls].sum+tr[rs].sum+tr[rt].point.val;
            tr[rt].sz=tr[ls].sz+tr[rs].sz+1;
            for(res i=0;i<=1;i++){
                tr[rt].mn[i]=min({tr[ls].mn[i],tr[rs].mn[i],tr[rt].point.x[i]});
                tr[rt].mx[i]=max({tr[ls].mx[i],tr[rs].mx[i],tr[rt].point.x[i]});
            }
        }
        inline void slap(res rt,res num){
            if(tr[rt].son[0])slap(tr[rt].son[0],num);
            a[num+tr[tr[rt].son[0]].sz+1]=tr[rt].point,st[++top]=rt;
            if(tr[rt].son[1])slap(tr[rt].son[1],num+tr[tr[rt].son[0]].sz+1);
        }
        int build(res l,res r,res d){
            if(l>r)return 0;
            res rt=newnode(),mid=(l+r)>>1;
            D=d,nth_element(a+l,a+mid,a+r+1),tr[rt].point=a[mid];
            tr[rt].son[0]=build(l,mid-1,d^1),tr[rt].son[1]=build(mid+1,r,d^1);
            pushup(rt);
            return rt;
        }
        inline void check(res &rt,res d){
            if(alph*tr[rt].sz<tr[tr[rt].son[0]].sz||alph*tr[rt].sz<tr[tr[rt].son[1]].sz)slap(rt,0),rt=build(1,tr[rt].sz,d);
        }
        void insert(res &rt,const RG P &p,res d){
            if(!rt){
                rt=newnode(),tr[rt].init(p);
                return;
            }
            if(tr[rt].point.x[d]<p.x[d])insert(tr[rt].son[1],p,d^1);
            else insert(tr[rt].son[0],p,d^1);
            pushup(rt),check(rt,d);
        }
        int Rt;
#define XW const res &x1,const res &y1,const res &r
#define XWW x1,y1,r
#define XWWW tr[rt].point.x[0],tr[rt].point.x[1]
#define XWWWW const res &X1,const res &Y1
        inline bool bh(const res &rt,XW){
            res cnt=0;
            cnt+=(1ll*(x1-tr[rt].mn[0])*(x1-tr[rt].mn[0])+1ll*(y1-tr[rt].mn[1])*(y1-tr[rt].mn[1])<=1ll*r*r);
            cnt+=(1ll*(x1-tr[rt].mn[0])*(x1-tr[rt].mn[0])+1ll*(y1-tr[rt].mx[1])*(y1-tr[rt].mx[1])<=1ll*r*r);
            cnt+=(1ll*(x1-tr[rt].mx[0])*(x1-tr[rt].mx[0])+1ll*(y1-tr[rt].mn[1])*(y1-tr[rt].mn[1])<=1ll*r*r);
            cnt+=(1ll*(x1-tr[rt].mx[0])*(x1-tr[rt].mx[0])+1ll*(y1-tr[rt].mx[1])*(y1-tr[rt].mx[1])<=1ll*r*r);
            return cnt==4;
        }
        inline bool bh(XWWWW,XW){
            return 1ll*(x1-X1)*(x1-X1)+1ll*(y1-Y1)*(y1-Y1)<=1ll*r*r;
        }
        inline bool xj(res rt,XW){
            res x,y;
            if(tr[rt].mn[0]<=x1&&x1<=tr[rt].mx[0])x=x1;
            else if(tr[rt].mn[0]>x1)x=tr[rt].mn[0];
            else x=tr[rt].mx[0];
            if(tr[rt].mn[1]<=y1&&y1<=tr[rt].mx[1])y=y1;
            else if(tr[rt].mn[1]>y1)y=tr[rt].mn[1];
            else y=tr[rt].mx[1];
            return 1ll*(x1-x)*(x1-x)+1ll*(y1-y)*(y1-y)>1ll*r*r;
        }
        LL query(res rt,XW){
            if(!rt||xj(rt,XWW))return 0;
            if(bh(rt,XWW))return tr[rt].sum;
            res ret=0;
            if(bh(XWWW,XWW))ret+=tr[rt].point.val;
            return ret+query(tr[rt].son[0],XWW)+query(tr[rt].son[1],XWW);
        }
    }A;
    inline void MAIN(){
        A.tr[0].mn[0]=A.tr[0].mn[1]=inf,A.tr[0].mx[0]=A.tr[0].mx[1]=-inf;
        res T=read();
        while(T--){
            n=read(),A.tot=A.top=A.Rt=0;
            for(res i=1;i<=n;i++){
                res x=read(),y=read(),v=read(),r=read();
                A.insert(A.Rt,init(x,y,v),0),printf("%lld\n",A.query(A.Rt,x,y,r));
            }
        }
    }
}

[1003 Puzzle loop]

solution

题面：一张大小为 ​​ 的格点图，相邻的格点可以连边，每个小正方的四个格点边数之和被限制了奇偶，同时只能连出环，且连出的环不能有共边。问连边的方案数。

做法：连出的环不能有共边和只能连环的条件可以一同等价为每个点的点度为偶数。那么限制就可以用异或方程表示每条边是否出现了。最后跑个高斯消元，bitset 优化下消元过程即可。复杂度 。

//2021.7.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int n,m;
    char str[20];
    int idc[20][20],idl[20][20],idx,funcx;
    bitset<34*34+10> a[34*34+10];
    inline int gauss(){
        res nw=1;
        for(res i=1;i<idx;i++){
            res k=0;
            for(res j=nw;j<=funcx;j++)if(a[j][i]){k=j;break;}
            if(!k)continue;
            if(k^nw)swap(a[nw],a[k]);
            for(res j=1;j<=funcx;j++)if(nw^j&&a[j][i])a[j]^=a[nw];
            nw++;
        }
        for(res i=nw;i<=funcx;i++)if(a[i].any())return -1;
        return idx-nw;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read(),idx=0;
            for(res i=1;i<=n;i++)for(res j=1;j<m;j++)idc[i][j]=++idx;
            for(res i=1;i<n;i++)for(res j=1;j<=m;j++)idl[i][j]=++idx;
            idx++,funcx=0;
            for(res i=1;i<n;i++){
                scanf("%s",str+1);
                for(res j=1;j<m;j++){
                    if(str[j]!='.'){
                        bitset<34*34+10> &A=a[++funcx];
                        A.reset(),A[idc[i][j]]=A[idc[i+1][j]]=A[idl[i][j]]=A[idl[i][j+1]]=1,A[idx]=str[j]-'0';
                    }
                }
            }
            for(res i=1;i<=n;i++)for(res j=1;j<=m;j++){
                bitset<34*34+10> &A=a[++funcx];
                A.reset();
                if(i>1)A[idl[i-1][j]]=1;
                if(j>1)A[idc[i][j-1]]=1;
                if(i<n)A[idl[i][j]]=1;
                if(j<m)A[idc[i][j]]=1;
                A[idx]=0;
            }
            res t=gauss();
            printf("%d\n",t!=-1?qpow(2,t):0);
        }
    }
}

[1004 Another thief in a Shop]

solution

题面：物品体积小于等于 ，总背包体积 的无限背包问题。

做法：先讲个考场上的做法。

无限背包的问题可以利用 gf，即求 ​​​​​。而根据求逆的递推式，我们知道 ​​​​​ 具有一个齐次线性递推式，所以暴力 CH 即可。时间复杂度 ​​​​​，FFT 优化后可以做到 ​​​​​​​。但这个做法，前者跑不过去，后者还要任意模数，导致很难写，最后也没写完。

实际上，

​​​​​​​​​(​​ 为定值且小于 ​​​) 是一个关于 ​​ 的 ​​​ 次多项式。

数学归纳，我们假定当前已经满足情况，现加入 ​​​​。

设 ​​。

显然有 ​​​​​​​​​。根据归纳假设，有 ​​​​​​​​​​​。

那么

已经被 ljc 鸽鸽教会了。

设 ​​​​​。

但我们不像之前那样转移，而是考虑 ​​，我们可以得到一个递推式：​。

考虑按照这个递推式继续递推，再加上归纳假设，就有

$$\begin{align*} &f'_{(m+a)l'+t}=f_t+\sum_{x=0}^m \sum_{j=1}^p f_{xl'+t+ja_n}\\ &=f_t+\sum_{j=1}^p\sum_{x=0}^m \sum_{i=0}^{n-1} a_{(t+ja_n)\mod l,i} (qx+\lfloor\frac{t+ja_n}{l}\rfloor)^i\\ &=f_t+\sum_{j=1}^p\sum_{i=0}^{n-1} a_{(t+ja_n)\mod l,i}\sum_{x=0}^m \sum_{o=0}^i \binom{i}{o}q^ox^o\lfloor\frac{t+ja_n}{l}\rfloor^{i-o}\\ &=f_t+\sum_{j=1}^p\sum_{i=0}^{n-1} a_{(t+ja_n)\mod l,i} \sum_{o=0}^i \binom{i}{o}q^o\lfloor\frac{t+ja_n}{l}\rfloor^{i-o}\sum_{x=0}^m x^o\\ &=f_t+\sum_{i=0}^{n-1}\sum_{o=0}^i\binom{i}{o}q^o\sum_{j=1}^p a_{(t+ja_n)\mod l,i} \lfloor\frac{t+ja_n}{l}\rfloor^{i-o}g_{o+1}(m)\\ &=f_t+\sum_{i=0}^{n-1}\sum_{o=0}^i\binom{i}{o}q^og_{o+1}(m)b_{i,o}\\ &=f_t+\sum_{i=0}^{n-1}h_{i+1}(m)\\ &=f_t+d_n(m) &\end{align*}$$

其中 表示关于 的次数为 的多项式。

于是我们证明了上述性质，因此可以求出 的系数，拉格朗日插值即可。

时间复杂度 。

//2021.7.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=6e6+10;
namespace MAIN{
    int a[N];
    int lcm;
    int f[N];
    inline int Lagrange(res *y,res n,res k){
        res ret=0;
        for(res i=0;i<=n;i++){
            res tmp=1;
            for(res j=0;j<=n;j++){
                if(i==j)continue;
                tmp=mul(tmp,mul(Add(k,kcz-j),qpow(Add(i,kcz-j))));
            }
            add(ret,mul(tmp,y[i]));
        }
        return ret;
    }
    int y[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read();
            RG LL k=Read();
            lcm=1;
            for(res i=1;i<=n;i++)a[i]=read(),lcm=lcm*a[i]/__gcd(lcm,a[i]);
            res t=int(k%lcm);
            res p=t+n*lcm;
            f[0]=1;
            for(res i=1;i<=p;i++)f[i]=0;
            for(res i=1;i<=n;i++)for(res j=a[i];j<=p;j++)add(f[j],f[j-a[i]]);
            for(res i=0;i<=n;i++)y[i]=f[i*lcm+t];
            printf("%d\n",Lagrange(y,n,int(k/lcm%kcz)));
        }
    }
}

[1005 Minimum spanning tree]

solution

题面：点的编号从 到 ​，求边权为点编号最小公约数的最小生成树。

做法：每个质数向 连边，合数向自己最小质因数连边，就结束了。复杂度 。​

//2021.7.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=10000000+10;
namespace MAIN{
    int prim[N],tot,vis[N];
    LL sum[N];
    inline void MAIN(){
        for(res i=2;i<=N-10;i++){
            if(!vis[i])prim[++tot]=i;
            for(res j=1;j<=tot&&1ll*prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0)break;
            }
        }
        for(res i=3;i<=N-10;i++)sum[i]=sum[i-1]+(vis[i]?i:2*i);
        res T=read();
        while(T--)printf("%lld\n",sum[read()]);
    }
}

[1006 Xor sum]

solution

题面：给一组数，找到一段最短的区间（最向左），使得异或和大于等于 。

做法：区间异或和等于两点前缀异或和的异或，于是每次枚举右端点，在 Trie 上找最靠右且合法的左端点即可。复杂度 ​。

//2021.7.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 sum[N],n;
    int mx[N*30],tr[N*30][2],tot,rt;
    inline int newnode(){
        tot++,tr[tot][0]=tr[tot][1]=0,mx[tot]=-n;
        return tot;
    }
    inline void insert(const res &x,const res &I){
        if(!rt)rt=newnode();
        res now=rt;
        for(res i=30;~i;i--){
            res d=(x>>i)&1;
            mx[now]=max(mx[now],I);
            if(!tr[now][d])tr[now][d]=newnode();
            now=tr[now][d];
        }
        mx[now]=max(mx[now],I);
    }
    int k;
    int dfs(res now,const res &r,res dep){
        if(!now)return -n;
        if(dep<0)return mx[now];
        if((k>>dep)&1)return dfs(tr[now][((r>>dep)&1)^1],r,dep-1);
        return max(mx[tr[now][((r>>dep)&1)^1]],dfs(tr[now][(r>>dep)&1],r,dep-1));
    }
    int ansl,ansr;
    inline void ck(res &ans,const res &r,const res &l){
        if(ans>r-l)ansl=l,ansr=r,ans=r-l;
    }
    inline void MAIN(){
        mx[0]=-inf;
        res T=read();
        while(T--){
            n=read(),k=read(),tot=rt=0,insert(0,0);
            res ans=n+1;
            for(res i=1;i<=n;i++)sum[i]=sum[i-1]^read(),ck(ans,i,dfs(rt,sum[i],30)),insert(sum[i],i);
            if(ans==n+1)puts("-1");
            else printf("%d %d\n",ansl+1,ansr);
        }
    }
}

[1007 Pass!]

solution

题面： 个人在传球，一开始球在 ​​ 号手上，每一秒传给其他人，设第 秒传到 号的方案数为 。现告诉你 ，希望求出最小的 。

做法：先考虑知道 算 的情况，容易写出 dp ： 为第 秒到 号手上的方案数， 为第 秒到其他人手上的方案数，转移就是 。发现我们求 就是在求 。于是改一下转移，则是 。边界情况注意下即可。

注意到这个递推式可以用特征方程解出，即 。于是讨论 的奇偶性就将题目转化为标准的 bsgs。套上板子即可。

我用了 map 被卡常了，建议手写 hash。

复杂度 ​。​

//2021.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    const int HashMod=100007;
    struct HashTable
    {
        struct Line{int u,v,next;}e[1000000];
        int h[HashMod],cnt;
        void Add(int u,int v,int w){e[++cnt]=(Line){w,v,h[u]};h[u]=cnt;}
        void Clear(){memset(h,0,sizeof(h));cnt=0;}
        void Hash(int x,int k)
        {
            int s=x%HashMod;
            Add(s,k,x);
        }
        int Query(int x)
        {
            int s=x%HashMod;
            for(int i=h[s];i;i=e[i].next)
                if(e[i].u==x)return e[i].v;
            return -1;
        }
    }Hash;
    inline int Solve(int y,int z,int p)
    {
        if(y%p==0){return -1;}
        y%=p;z%=p;
        if(z==1){return 0;}
        int m=int(sqrt(p))+1;Hash.Clear();
        for(RG int i=0,t=z;i<m;++i,t=mul(t,y))Hash.Hash(t,i);
        for(RG int i=1,tt=qpow(y,m),t=tt;i<=m+1;++i,t=mul(t,tt))
        {
            int k=Hash.Query(t);
            if(k==-1)continue;
            return i*m-k;
        }
        return -1;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read(),x=read();
            if(x==1){printf("%d\n",0);continue;}
            if(x==0){puts("1");continue;}
            //g[i]=C_1\ast (n-1)^i+C_2\ast (-1)^i
            //C_1=\frac{n-1}{n}
            //C_2=-\frac{n-1}{n}
            x=mul(x,mul(n,qpow(n-1)));
            RG LL ans=-2;
            //i=2*i'
            {
                res b=Add(x,1),a=qpow(n-1,2);
                RG LL i=Solve(a,b,kcz);
                if(i!=-1)ans=2ll*i;
            }
            //i=2*i'+1
            {
                res b=Add(x,kcz-1),a=qpow(n-1,2);
                b=mul(b,qpow(n-1));
                RG LL i=Solve(a,b,kcz);
                if(i!=-1){
                    if(ans==-2)ans=2ll*i+1;
                    else ans=min(ans,2ll*i+1);
                }
            }
            printf("%lld\n",ans+1);
        }
    }
}

[1008 Maximal submatrix]

solution

题面： 大小的图，每个位置有一个数字，希望找到一个面积最大的矩形，使得矩形的每一列从上向下不增。

做法：冷静一下，所谓悬线法怎么就是个单调栈啊。枚举每一行，再枚举下端点，维护个不减的单调栈就行了。复杂度 。

//2021.7.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
    int a[N][N];
    int f[N];
    int top,st[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read(),m=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)a[i][j]=read();
            res ans=0;
            for(res i=1;i<=m+1;i++)f[i]=0;
            for(res i=1;i<=n;i++){
                for(res j=1;j<=m;j++)if(a[i][j]>=a[i-1][j])f[j]++;else f[j]=1;
                top=0;
                for(res j=1;j<=m+1;j++){
                    while(top&&f[st[top]]>f[j])ans=max(ans,(j-st[top-1]-1)*f[st[top]]),top--;
                    st[++top]=j;
                }
            }
            printf("%d\n",ans);
        }
    }
}

[1009 KD-Graph]

solution

题面： 个点 条边的无向连通图，有边权，希望将 个点划入 个集合，满足相同集合内的点之间存在一条路径使得最大边权小于等于 ，不同集合的点之间不存在一条路径使得最大边权小于等于 ，求最小的 。

做法：我们假定已经划分好 ​ 个集合了，那么容易证明 ​​ 要小于连接不同集合的边的最小边权。另一方面，我们先给每个集合内求个最小生成树，那么 ​ 一定要大于最小生成树上的最大边权。由此来看，我们不妨直接求最小生成树，当连通块数等于 ​ 时停止。根据上述对 ​ 的限制可以证明此时最优，同时也可以验证是否有解了。时间复杂度 ​。

//2021.7.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    struct E{
        int u,v,w;
        E() {}
        E(res u,res v,res w):u(u),v(v),w(w) {}
        inline bool operator < (const RG E &B) const{
            return w<B.w;
        }
    }edge[N];
    int fa[N];
    inline int find(res x){
        while(x!=fa[x])x=fa[x]=fa[fa[x]];
        return x;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read(),m=read(),k=read();
            for(res i=1;i<=n;i++)fa[i]=i;
            for(res i=1;i<=m;i++){
                res u=read(),v=read(),w=read();
                edge[i]=E(u,v,w);
            }
            sort(edge+1,edge+m+1);
            res cur=n;
            if(k==n){puts("0");continue;}
            RG bool fl=0;
            for(res i=1;i<=m;){
                res j=i;
                while(edge[j].w==edge[i].w&&j<=m)j++;
                for(res o=i;o<j;o++){
                    res fu=find(edge[o].u),fv=find(edge[o].v);
                    if(fu==fv)continue;
                    cur--,fa[fu]=fv;
                }
                if(cur==k){printf("%d\n",edge[i].w),fl=1;break;}
                i=j;
            }
            if(!fl)puts("-1");
        }
    }
}

[1010 zoto]

solution

题面：二维平面上 个点坐标为 ​，每次询问给出一个矩形，求矩形所覆盖的点中 坐标不同的有几个？

做法：我开始读错题，后来廷廷接手写了二维线段树，然后两个 就被卡常了。。。中途已经猜到自己在走偏路了，以为正解一个 ​，就忘记莫队是什么了。。签到失败确实是意料之外了。

按 ​ 坐标写个莫队，​ 坐标随便拿个分块维护一下就结束了，不知道现场在做什么。时间复杂度 ​。​

//2021.7.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,q;
    int a[N];
    int block;
    struct Q{
        int l,r,d,u,id;
        Q() {}
        Q(res l,res r,res d,res u,res id):l(l),r(r),d(d),u(u),id(id) {}
        inline bool operator < (const RG Q &B) const {
            return l/block==B.l/block?r<B.r:l/block<B.l/block;
        }
    }que[N];
    int num[N],sum[N];
    inline void add(const res &x){
        if(++num[x]==1)sum[x/block]++;
    }
    inline void dec(const res &x){
        if(--num[x]==0)sum[x/block]--;
    }
    int ans[N];
    inline int calc(const res &o){
        res ret=0;
        for(res i=0;i<o/block;i++)ret+=sum[i];
        for(res i=o/block*block;i<=o;i++)ret+=(num[i]>=1);
        return ret;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),q=read(),block=int(sqrt(100000)+1);
            for(res i=0;i<=100000;i++)num[i]=sum[i]=0;
            for(res i=1;i<=n;i++)a[i]=read();
            for(res i=1;i<=q;i++){
                res l=read(),d=read(),r=read(),u=read();
                que[i]=Q(l,r,d,u,i);
            }
            sort(que+1,que+q+1);
            for(res p=0,i=1;p<=n/block;p++){
                res j=i;
                while(que[j].l/block==p&&j<=q)j++;
                if(j==i)continue;
                for(res k=0;k<=100000;k++)num[k]=sum[k]=0;
                res l=que[i].l,r=que[i].r;
                for(res k=l;k<=r;k++)add(a[k]);
                ans[que[i].id]=calc(que[i].u)-calc(que[i].d-1);
                for(res k=i+1;k<j;k++){
                    while(r<que[k].r)add(a[++r]);
                    while(l<que[k].l)dec(a[l++]);
                    while(l>que[k].l)add(a[--l]);
                    ans[que[k].id]=calc(que[k].u)-calc(que[k].d-1);
                }
                i=j;
            }
            for(res i=1;i<=q;i++)printf("%d\n",ans[i]);
        }
    }
}

[1011 Necklace of Beads]

solution

题面：给环上 ​​ 个点染三种颜色，相同颜色不相邻，其中第三种颜色出现次数需小于等于 ，旋转视为同构，问染色方案数。

做法：Burnside Polya 啥的忘得差不多了，之后再补。

根据 Burnside 引理，写出 ​​，​​​ 表示循环大小为 ​​ 的合法染色方案。而由于第三种颜色的个数限制，我们枚举第三种颜色的个数，即

$$\large ans=\frac{1}{n} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{\gcd(i,n)})}\rfloor} g_{\gcd(i,n),j}\\\\$$

其中 表示循环大小为 且第三种颜色用了 次的合法染色方案，也即环大小为 ​​ 且第三种颜色用了 次的合法染色方案。

我们现考虑已经染好了第三种颜色，那么每两个第三种颜色之间的染色方案是只有两种的（因为确定一个之后，相邻的全部确定，由此确定一个间隔的方案）。因此 ​，其中 ​ 表示环大小为 ​ 染了 ​ 个不相邻位置的方案数。​ 可以根据第 ​ 个位置是否染色（转成序列问题，然后隔板法）来得到 ​（ 为 时则看 的奇偶）。由此我们推出了 ​ 的表达式。

于是原式就转成了一个推式子问题了。

$$\begin{align*} &ans=\frac{1}{n} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{\gcd(i,n)})}\rfloor} g_{\gcd(i,n),j}\\ &=\frac{1}{n} \sum_{d=1}^n \sum_{i=0}^n [\gcd(i,n)=d]\sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{d})}\rfloor} g_{d,j}\\ &=\frac{1}{n} \sum_{d=1}^n \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{d})}\rfloor} g_{d,j}\sum_{i=0}^n [\gcd(i,n)=d]\\ &=\frac{1}{n} \sum_{d,d|n} \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{d})}\rfloor} g_{d,j}\sum_{i,d|i}^n [\gcd(\frac{i}{d},\frac{n}{d})=1]\\ &=\frac{1}{n} \sum_{d,d|n} \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{d})}\rfloor} g_{d,j}\sum_{i=1}^{\frac{n}{d}} [\gcd(i,\frac{n}{d})=1]\\ &=\frac{1}{n} \sum_{d,d|n} \sum_{j=0}^{\lfloor\frac{k}{(\frac{n}{d})}\rfloor} g_{d,j}\varphi(\frac{n}{d})\\ &=\frac{1}{n} \sum_{d,d|n} \varphi(\frac{n}{d})F(d)\\ &=\frac{1}{n} (\varphi\ast F)(n) &\end{align*}$$

这样枚举 ​ 直接暴力求解复杂度就很小了，具体多小我也算不清了，能过就算成功。

//2021.7.23 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 fac[N],inv[N],pinv[N];
    inline int C(const res &x,const res &y){
        return x<y?0:mul(fac[x],mul(pinv[y],pinv[x-y]));
    }
    int phi[N],pw[N];
    int prim[N],tot,vis[N];
    inline int F(const res &d,const res &k,const res &n){
        res ret=(d&1)?0:2;
        for(res j=1;j<=k/(n/d);j++)add(ret,mul(pw[j],Add(C(d-j-1,j-1),C(d-j,j))));
        return ret;
    }
    inline void MAIN(){
        fac[0]=fac[1]=inv[0]=inv[1]=pinv[0]=pinv[1]=pw[0]=1,pw[1]=2;
        for(res i=2;i<=N-10;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i),pw[i]=Add(pw[i-1],pw[i-1]);
        for(res i=2;i<=N-10;i++)pinv[i]=mul(pinv[i-1],inv[i]);
        phi[1]=1;
        for(res i=2;i<=N-10;i++){
            if(!vis[i])phi[i]=i-1,prim[++tot]=i;
            for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0){phi[prim[j]*i]=phi[i]*prim[j];break;}
                phi[prim[j]*i]=phi[i]*(prim[j]-1);
            }
        }
        res T=read();
        while(T--){
            res n=read(),k=read(),ans=0;
            for(res d=1;d<=n;d++)if(n%d==0)add(ans,mul(phi[n/d],F(d,k,n)));
            printf("%d\n",mul(ans,inv[n]));
        }
    }
}