1175. Disposition des nombres premiers / échange de doigts II 104. Nombre de permutations

1175. Disposition des nombres premiers【Questions simples】【Une question par jour】

Idées：

Trouver le nombre de nombres premiersk1,n-k1Trouver le nombre de nombres non premiersk2,Le nombre de types conformes est k1Factoriel de * k2Factoriel de,Parce que le résultat de l'opération peut être hors de portée,Par conséquent, le résultat de l'opération est calculé en fonction de la signification du problème.10^9+7Module.
Mise en place MOD = 10^9+7,Par conséquent, les résultats ci - dessus peuvent être exprimés comme suit:：

ans = (k1! * k2!) % MOD

Parce que les opérations Factorielles peuvent également dépasser les limites,Par conséquent, la formule ci - dessus est transformée mathématiquement

ans = (k1! * k2!) % MOD
	= ((k1! % MOD) * (K2! % MOD)) % MOD
	//【】Représente la multiplication cumulative
	= ((【k1i % MOD】 % MOD ) * (【k2i % MOD】 % MOD ) ) % MOD
	= (【k1i % MOD】 * 【k2i % MOD】) % MOD

Code：

class Solution {
    
    static int MOD = (int) 1e9+7;
    public int numPrimeArrangements(int n) {
    
        if (n <= 2){
    
            return 1;
        }
        int k1 = 1;
        for (int i = 3; i <= n; i++) {
    
            if (isPrime(i)){
    
                k1++;
            }
        }
        int k2 = n - k1;
        long ans = 1;
        for (int i = 2; i <= k1; i++) {
    
            ans = ans * i % MOD;
        }
        for (int i = 2; i <= k2; i++) {
    
            ans = ans * i % MOD;
        }
        return (int) (ans);
    }
    public boolean isPrime(int n){
    
        int k = (int) Math.sqrt(n);
        for (int i = 2; i <= k ; i++) {
    
            if (n % i == 0){
    
                return false;
            }
        }
        return true;
    }
}

---

Un doigt d'épée. Offer II 104. Nombre de rangées【Question moyenne】

Idées：【Planification dynamique】

Dupé par la formule du sac à dos complet d'hier ~, Ce n'est pas un problème de sac à dos

Code：

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        //DéfinitiondpTableau,dp[i]Représenté et représenté pariNombre de combinaisons
        int[] dp = new int[target+1];
        //Conditions limites i = 0Heure,Et pour0 Il n'y a qu'une seule combinaison de   Ne sélectionnez Aucun élément ,Donc,dp[0] = 1
        dp[0] = 1;
        //Équation de transfert
        for (int i = 1; i <= target; i++) {
    
            for (int num : nums) {
    
                //TraverséenumsTableau, Si la cible et i Supérieur ou égal à la valeur actuelle de l'élément num, Description cet élément peut être sélectionné dp[i] La valeur de est égale à tout ce qui est satisfait dans le tableau i>=numDedpLa somme des valeurs
                if (i >= num) {
    
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}