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

C 小红的二叉树

考虑以每个节点为中间节点的路径，第一层的节点有一条路径，叶子结点没有，而中间节点的路径有三条，因此答案为pow(2,n-1)*3-5，但是要特判n为1的情况，时间复杂度O(n)

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();
        System.out.println(n==1?0:(pow(2,n-1)*3-5+mod)%mod);
    }
    static long pow(long a,long b){
        return b==0?1:pow(a,b-1)*a%mod;
    }
}

D 小红的“质数”寻找

方法一：按照视频讲解里的方法，构造开头，后边全是0的数，时间复杂度(Tlen(x))

import java.util.*;
public class Main{
    static int start[]={2,3,5,5,7,11};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            String x=sc.next();
            System.out.print(start[Math.min(x.charAt(0)-'0'-1,5)]);
            for(int j=x.length();j>1;j--){
                System.out.print(0);
            }
            System.out.println();
        }
    }
}

方法二：用高精度（或者大数类），按照末尾几位为规律分组尝试，在本题的测试例子中，我只将末尾的4位进行了尝试就得到的正确答案（但是严格来说，遇到大的数据，复杂度不正确）

import java.util.*;
import java.math.*;
public class Main{
    static BigInteger tenKilo=new BigInteger("10000");
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        //200万以内的质数之间的最大距离是148
        for(int i=sc.nextInt();i!=0;i--){
            BigInteger bi=new BigInteger(sc.next()),doubleBi=bi.add(bi);
            boolean found=false;
            while(!found&&bi.compareTo(doubleBi)<=0){
                int re=bi.mod(tenKilo).intValue(),sum=find(bi);
                for(int j=re;j<10000;j++){
                    if(check(sum-re%10-re/10%10-re/100%10-re/1000+j%10+j/10%10+j/100%10+j/1000)&&bi.add(new BigInteger(j-re+"")).compareTo(doubleBi)<=0){
                        System.out.println(bi.add(new BigInteger(j-re+"")));
                        found=true;
                        break;
                    }
                }
                bi=bi.add(new BigInteger(10000-re+""));
            }
        }
    }
    static int find(BigInteger bi){
        int ans=0;
        for(char c:bi.toString().toCharArray()){
            ans+=c-'0';
        }
        return ans;
    }
    static boolean check(int a){
        if(a<2){
            return false;
        }
        for(int i=2;i*i<=a;i++){
            if(a%i==0){
                return false;
            }
        }
        return true;
    }
}

而对于在100万以内，距离最大的相邻质数对是 492113 和 492227，它们之间的距离为 114，因此构造如下hack数据即可过滤掉上述代码：[9]*54692+[0]*100，成功TLE，最大尝试次数可达O(1e12~1e13)

E 小红的好排列

对于下标为3的倍数的位置，放置何种数字均可以，而对于剩下的指标（非3的倍数下标），一部分需要填充3的倍数，一部分需要填充非3的倍数，将每一部分按照排列组合算出即可，时间复杂度O(nlog(mod))，代码为化简版：

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();
        System.out.println(pow(fac(n/3)*fac(n-n/3)%mod,2)*pow(fac(n/3*2-n/2)*pow(fac(n/2-n/3),2)%mod*fac(n-n/2)%mod,mod-2)%mod);
    }
    static long fac(int a){
        return a<0?0:a==0?1:fac(a-1)*a%mod;
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}

F 小红的小球染色期望

采用分治的思想，对于无法再次进行操作的局面，一定是一些孤立的单个未上色小球，且不相邻，那么对于剩余n个小球情况，取得每种位置的可能数为n-1种，而剩下的期望即为左边空余小球的期望+有右边空余小球的期望，因此利用递推+前缀和的思想即可，时间复杂度O(nlog(mod))

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();
        long ans=0,sum=0;
        for(int i=2;i<=n;i++){
            long cur=ans;
            ans=(1+sum*2*pow(i-1,mod-2))%mod;
            sum=(sum+cur)%mod;
        }
        System.out.println(ans);
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}