题解 | 牛客小白月赛116 CDEFG Java题解

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

C Poi 的新加法（Easy Version） && F Poi 的新加法（Hard Version）

可知，f(x,y)=(x&y)<<1，因此，最多经过60次，结果就恒为0，时间复杂度，O(T(n+60q))

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=Integer.parseInt(bf.readLine());i!=0;i--){
            StringTokenizer st=new StringTokenizer(bf.readLine());
            int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken());
            long a[]=new long[n];
            st=new StringTokenizer(bf.readLine());
            for(int j=0;j<n;j++){
                a[j]=Long.parseLong(st.nextToken());
            }
            for(int j=0;j<q;j++){
                st=new StringTokenizer(bf.readLine());
                int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken());
                long ans=a[l-1];
                for(int p=l;p<r&&ans!=0;p++){
                    ans=(ans&a[p])<<1;
                }
                bw.write(ans+"\n");
            }
        }
        bw.flush();
    }
}

D Poi 的消消乐

参考资料，时间复杂度O(Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),count1=0,count2=0;
            String s=sc.next();
            for(int j=1;j<n;j++){
                if(s.charAt(j)!=s.charAt(j-1)){
                    count1++;
                }
                if(count1==1){
                    count2++;
                }
            }
            System.out.println(count1==0?1:count1==1?Math.min(4,1+count2):2);
        }
    }
}

E 旷课大师

略

G 经典 DP

先经过背包，算出每种和对m取余数的子集的方案数，再用矩阵快速幂利用初始转移矩阵加速运算，时间内复杂度O(m(n+m^2logt))

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        int c=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt(),t=sc.nextInt(),count[]=new int[m];
        count[0]=1;
        for(int b:a){
            int temp[]=new int[m];
            for(int j=0;j<m;j++){
                temp[(j+b)%m]=(temp[(j+b)%m]+count[j])%mod;
            }
            for(int j=0;j<m;j++){
                count[j]=(temp[j]+count[j])%mod;
            }
        }
        count[0]=(count[0]+mod-1)%mod;
        long ans[]=new long[m],matrix[][]=new long[m][m];
        //mat[i][j]表示的是计算i处的后值，需要多少倍的j处的前值
        for(int j=0;j<m;j++){
            for(int p=0;p<m;p++){
                matrix[p*j%m][j]=(matrix[p*j%m][j]+count[p])%mod;
            }
        }
        ans[c%m]=1;
        for(;t!=0;t>>=1,matrix=square(matrix)){
            if(t%2==1){
                ans=multiply(matrix,ans);
            }
        }
        System.out.println(ans[k]);
    }
    static long[] multiply(long a[][],long b[]){
        int m=a.length;
        long ans[]=new long[m];
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                ans[i]=(ans[i]+b[j]*a[i][j])%mod;
            }
        }
        return ans;
    }
    static long[][] square(long a[][]){
        int m=a.length;
        long ans[][]=new long[m][m];
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    ans[i][j]=(ans[i][j]+a[i][k]*a[k][j])%mod;
                }
            }
        }
        return ans;
    }
}