头像

lqd

武汉东湖学院




离线:5小时前


活动打卡代码 AcWing 893. 集合-Nim游戏

lqd
7小时前
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static int N = 110, M = 10010;
    static int n, m;
    static int[] s = new int[N], f = new int[M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        for (int i = 0; i < m; i ++ ) s[i] = sc.nextInt();
        n = sc.nextInt();
        Arrays.fill(f, -1);
        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            int x = sc.nextInt();
            res ^= sg(x);
        }
        if (res == 0) System.out.println("No");
        else System.out.println("Yes");
    }

    private static int sg(int x) {
        if (f[x] != -1) return f[x];

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i ++ ) {
            int sum = s[i];
            if (x >= sum) set.add(sg(x - sum));
        }
        for (int i = 0; i <= N; i ++ ) {
            if (!set.contains(i)) {
                return f[x] = i;
            }
        }
        return 0;
    }
}



活动打卡代码 AcWing 891. Nim游戏

lqd
9小时前
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        while (n -- > 0) {
            int x = sc.nextInt();
            res ^= x;
        }
        if (res == 0) System.out.println("No");
        else System.out.println("Yes");
    }
}


活动打卡代码 AcWing 890. 能被整除的数

lqd
1天前
import java.util.Scanner;

public class Main {

    static int N = 20;
    static int n, m;
    static int[] p = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i ++ ) p[i] = sc.nextInt();

        int res = 0;
        for (int i = 1; i < 1 << m; i ++ ) {
            int t = 1, cnt = 0;
            for (int j = 0; j < m; j ++ ) {
                if ((i >> j & 1) == 1) {
                    cnt ++;
                    if ((long)t * p[j] > n) {
                        t = -1;
                        break;
                    }
                    t *= p[j];
                }
            }
            if (t != -1) {
                if (cnt % 2 == 1) res += n / t;
                else res -= n / t;
            }
        }
        System.out.println(res);
    }
}



活动打卡代码 AcWing 888. 求组合数 IV

lqd
5天前
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 5000,cnt = 0;
    static int primes[] = new int[N];
    static int sum[] = new int[N]; 
    static boolean st[] = new boolean[N]; 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        get_primes(a);
        for(int i = 0 ; i  < cnt ; i ++) {//枚举每一个质因数
            int p = primes[i];
            sum[i] = get(a,p)-get(b,p)-get(a-b,p);//求出他的次方
        }
        ArrayList<Integer> list = getmul();
        for(int i = list.size()-1;i>=0;i--) System.out.print(list.get(i));
    }
    private static ArrayList<Integer> getmul() {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        for(int i = 0 ; i < cnt ; i ++) {//枚举每一个质数
            for(int j = 1; j <= sum[i]; j ++) {//枚举每一个质数要乘多少次
                list = mul(list,primes[i]);
            }
        }
        return list;
    }
    private static ArrayList<Integer> mul(ArrayList<Integer> list, int x) {//高精度乘法
        int t = 0;
        for(int i = 0 ; i < list.size(); i ++) {
            t+=list.get(i)*x;
            list.set(i, t%10);
            t = t/10;
        }
        while(t!=0) {
            list.add(t%10);
            t/=10;
        }
        return list;
    }
    private static int get(int x, int p) {//x!是有p1~pi这些质数的次方组成的
        int res = 0;//通过x/p得到1*2*...*x中,包含多少个p,通过x/p^2得到1*2*...*x中,包含多少个p^2,,,
        while(x!=0) {//将这些数目累加就可以算出组成x!中的其中一个p的次方
            res += x/p;
            x /= p;
        }
        return res;
    }
    private static void get_primes(int n) {//质数线性筛法
        for(int i = 2; i <= n ; i++) {
            if(!st[i]) primes[cnt++] = i;
            for(int j = 0 ; primes[j]<=n/i; j++) {
                st[primes[j]*i] = true;
                if(i%primes[j]==0) break;
            }
        }
    }
}


活动打卡代码 AcWing 887. 求组合数 III

lqd
5天前
import java.io.*;

class Main{
    static int p;

    //快速幂
    static int qmi(int a, int b){
        int res = 1 % p;
        while(b!=0){
            if(b%2!=0) res = (int) ((long)res*a%p);
            a = (int) ((long)a*a%p);
            b/=2;
        }
        return res;
    }

    static int C(long a, long b){
        int res = 1;
        for(int i=1, j=(int)a; i<=b; i++, j--){
            res = (int) ((long)res*j%p) ;
            res = (int) ((long)res*qmi(i, p-2)%p);
        }
        return res;
    }//根据定义求C(a, b)

    //lucas定理
    static int lucas(long a, long b){
        if(a<p && b<p){
            return C(a, b);
        }
        return (int) ((long)lucas(a/p, b/p)*C(a%p, b%p) % p);
    }

    public static void main(String[]args)throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(in.readLine());
        while(n-->0){
            String[]arr=in.readLine().split(" ");
            long a=Long.parseLong(arr[0]);
            long b=Long.parseLong(arr[1]);
            p=Integer.parseInt(arr[2]);

            System.out.println(lucas(a,b));
        }
    }
}


活动打卡代码 AcWing 886. 求组合数 II

lqd
5天前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010,mod = 1000000007;
    static long[] fact = new long[N];
    static long[] infact = new long[N];
    static Long qmi(int a,int k,int p)
    {
        long res = 1 % p;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % p;
            k >>= 1;
            t = t * t % p;
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        fact[0] = 1;
        infact[0] = 1;
        for(int i = 1;i < N;i++)
        {
            fact[i] = fact[i - 1] * i % mod;
            infact[i] = infact[i - 1] * qmi(i,mod - 2,mod) % mod;
        }

        int n = Integer.parseInt(reader.readLine().trim());
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            System.out.println(fact[a] * infact[a - b] % mod * infact[b] % mod);
        }
    }
}


活动打卡代码 AcWing 885. 求组合数 I

lqd
8天前
import java.util.Scanner;

public class Main {
    static int N = 2005,INF = 1000000007;
    static int C[][] = new int[N][N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for(int a = 0; a <= 2000;a++) {
            C[a][0] = 1;
            for(int b = 1 ; b <= a;b ++) {
                C[a][b] = (C[a-1][b]+C[a-1][b-1])%INF;
            }
        }
        int n = scanner.nextInt();
        while(n-->0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(C[a][b]);
        }
    }
}



活动打卡代码 AcWing 458. 比例简化

lqd
9天前
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int L = sc.nextInt();
        int a = 0;
        int b = 1;
        double delta = 1e9;
        for (int i = 0; i <= L; i ++ )
            for (int j = 1; j <= L; j ++ )
            {
                double x = (double) i / j;
                double X = (double) A / B;
                if (x >= X && x - X < delta)
                {
                    delta = x - X;
                    a = i;
                    b = j;
                }
            }
        System.out.println(a + " " + b);
    }
}



lqd
9天前
import java.util.Scanner;
public class Main
{
    static Scanner in = new Scanner(System.in);
    static int N = 110;
    static int a[][] = new int[N][N];
    static int n;

    static void swap(int r1, int c1, int r2, int c2)
    {
        int t = a[r1][c1];
        a[r1][c1] = a[r2][c2];
        a[r2][c2] = t;
    }

    static int gauss()
    {
        int r, c;
        for (r = c = 0; c < n; c++)
        {
            int t = r;
            for (int i = r; i < n; i++)
                if (a[i][c] == 1)
                {
                    t = i;
                    break;
                }
            if (a[t][c] == 0) continue;
            for (int i = c; i <= n; i++) swap(t, i, r, i);
            for (int i = r + 1; i < n; i++)
                if (a[i][c] == 1)
                    for (int j = c; j <= n; j++)
                        a[i][j] ^= a[r][j];
            r++;
        }
        if (r < n)
        {
            for (int i = r; i < n; i++)
                if (a[i][n] == 1) return 2;
            return 1;
        }
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                a[i][n] ^= a[j][n] & a[i][j];
        return 0;
    }

    public static void main(String args[])
    {
        n = in.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= n; j++) a[i][j] = in.nextInt();
        int t = gauss();
        if (t == 0)
            for (int i = 0; i < n; i++) System.out.println(a[i][n]);
        else System.out.println(t == 1 ? "Multiple sets of solutions" : "No solution");
    }

}



lqd
11天前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Gauss {
    static int N = 110;
    static double eps = 1e-6;
    static int n;
    static double a[][] = new double[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        for (int i = 0; i < n; i ++ )
        {
            String[] str = bf.readLine().split(" ");
            for (int j = 0; j < n + 1; j ++ )
                a[i][j] = Double.parseDouble(str[j]);
        }

        int t = gauss();

        if (t == 0)
        {
            for (int i = 0; i < n; i ++ )
                System.out.printf("%.2f\n", a[i][n]);
        }
        else if (t == 1) System.out.println("Infinite group solutions");
        else System.out.println("No solution");
    }

    private static int gauss() {
        int c;//列
        int r;//行
        //枚举每一列c
        for (c = 0, r = 0; c < n; c ++ )
        {
            //1.找到绝对值最大的一行
            int t = r;//t为绝对值最大的一行
            //遍历每一行
            for (int i = r; i < n; i ++ )
                //比较每一行第c列的值
                if (Math.abs(a[i][c]) > Math.abs(a[t][c]))
                    t = i;//如果找到比之前更大的就更新t值
            //如果绝对值为0,那么这一列所有数都为0,没有必要继续运算
            if (Math.abs(a[t][c]) < eps) continue;
            //2.将绝对值最大的这一行换到最上面
            //从第c列开始是因为第0 ~ c-1列都为0,不需要继续进行交换
            for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);
            //3.将绝对值最大的这一行的第一个系数变为1
            //即等号两边同时除以这个系数,如果从前往后除那么第一个系数除完后为1,后面的也都是除以1了,所以要从后往前除
            for (int i = n; i >= c; i --) a[r][i] /= a[r][c];
            //4.将绝对值最大的这一行的下面所有行的第c列变为0
            for (int i = r + 1; i < n; i ++ )
                if (Math.abs(a[i][c]) > eps) //如果是非0再操作,剪枝
                    //从后往前,当前行的每个数字,都减去对应列 * 行首非0的数字,这样就能保证第一个数字是 a[i][0] -= 1*a[i][0]
                    for (int j = n; j >= c; j -- )
                        a[i][j] -= a[r][j] * a[i][c];
            r ++;//更新r
        }

        //高斯消元后成上三角形式,再迭代回去求解
        //说明剩下的方程小于n个,不是唯一解
        if (r < n)
        {
            //从r ~ n - 1行可能是0 = 非0 或者 0 = 0
            for (int i = r; i < n; i ++ )
                if (Math.abs(a[i][n]) > eps) return 2;//无解
            return 1;//无穷解
        }

        //只有r = n 才是n个方程n个未知数才会有唯一解,迭代求解
        for (int i = n - 1; i >= 0; i -- )
            for (int j = i + 1; j < n; j ++ )
                //要用后面的方程带入前面的方程求解,将前面的方程的未知数变为一个,也就是其他的未知数的系数为0,也就是a[i][n]要减去后面方程倍数的Xn
                a[i][n] -= a[j][n] * a[i][j];
        return 0;//唯一解
    }

    private static void swap(double a, double b) {
        double t = b;
        b = a;
        a = t;
    }
}