C~F Java题解，代码已去除冗余~~~

C 小苯的01矩阵构造

首先证明sumr和sumc一定是同奇偶性的，因为两个数的奇偶性跟所有1的个数的奇偶性是相同的，也就是k必须是偶数，因此得证；那么对于k==sumr+sumc，只需在对角线上放置k/2个1，即可，时间复杂度O(n^2)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        if(k%2==1){
            System.out.println(-1);
        }
        else{
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(i==j&&i<k/2?1:0);
                }
                System.out.println();
            }
        }
    }
}

D 小苯的重排构造

n个数字一共n-1个数字，而相邻的数字gcd只可以是1或者2，而2只能由相邻的2组成；首先特判全1的组合，此时k只能是n-1；在众多相邻gcd中，有k-n+1个2，这些由k-n+2个2组成，以及2n-2-k个1，这些可以由12交替，之后剩下的1收尾组成，一次判断1和2的个数是否在正常范围内即可，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),count[]=new int[3];
        for(int i=0;i<n;i++){
            count[sc.nextInt()]++;
        }
        //一共n-1个数，其中k-n+1个2，2n-2-k个1，因此数组先有k-n+2个2，然后是12交替，生效的2不能多于1的个数
        if(k<n-1||k>n*2+2||count[2]==0&&k!=n-1||count[2]<k-n+2||count[2]-k+n-2>count[1]){
            System.out.println(-1);
        }
        else{
            for(int i=0;i<k-n+2;i++,count[2]--,System.out.print("2 ")){}
            for(;count[1]>0||count[2]>0;System.out.print(count[1]-->0?"1 ":""),System.out.print(count[2]-->0?"2 ":"")){}
        }
    }
}

E 小苯的xor图

拆出二进制位计算贡献，对于每一条边，在双向加边的时候，直接计算即可，时间复杂度O(18(n+m))

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),count[][]=new int[n+5][33],num[]=new int[n+5],w[]=new int[n+5];
        for(int i=1;i<=n;i++){
            w[i]=sc.nextInt();
        }
        long ans=0;
        for(int i=0;i<m;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            ans=(ans+find(u,v,w,num,count)+find(v,u,w,num,count))%mod;
        }
        System.out.println(ans);
    }
    static long find(int a,int b,int w[],int num[],int count[][]){
        long ans=0;
        for(int i=0;i<31;i++){
            ans+=(1L<<i)*(((w[a]^w[b])>>i&1)==0?count[a][i]:num[a]-count[a][i]);
            count[a][i]+=w[b]>>i&1;
        }
        num[a]++;
        return ans;
    }
}

F 小苯的前缀gcd构造

前缀的gcd一定是首项的一个约数，那么只需要反向构造出后缀最小的约数序列即可，每一项的前缀gcd就是自己，这样可以BFS预处理所有的组合并记录路劲，时间复杂度O(50^5+T(n+m))

import java.util.*;
public class Main{
    static int last[][][][]=new int[55][55][2505][];
    static{
        Queue<int[]> q=new LinkedList<>();
        for(int i=1;i<=50;i++){
            q.add(new int[]{i,i});
            last[1][i][i]=new int[2];//[上一个末尾，上一个和]
        }
        for(int i=1;i<50;i++){
            for(int p=q.size();p!=0;p--){
                int a[]=q.poll();
                for(int j=a[0];j+a[1]<=2500&&j<=50;j+=a[0]){
                    if(last[i+1][j][j+a[1]]==null){
                        last[i+1][j][j+a[1]]=a;
                        q.add(new int[]{j,j+a[1]});
                    }
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),m=sc.nextInt(),x=sc.nextInt();
            boolean found=false;
            for(int j=1;j<=m;j++){
                if(last[n][j][x]!=null){
                    found=true;
                    for(int k=n,cur[]=new int[]{j,x};k!=0;cur=last[k][cur[0]][cur[1]],k--){
                        System.out.print(cur[1]-last[k][cur[0]][cur[1]][1]+" ");
                    }
                    System.out.println();
                    break;
                }
            }
            if(!found){
                System.out.println(-1);
            }
        }
    }
}