AtCoder ABC156 Problème D Calcul et séquence du module Bouquet, etc.

Aperçu

AtCoder ABC156 Problème D J'ai essayé Bouquet. Disposition de l'élément inverse de mod et calcul de combinaison d'ordre de mod.

Contexte

J'ai été tellement occupé par le travail pendant un certain temps que j'ai été déçu de ne même pas pouvoir participer au concours, mais depuis que je m'étais installé, j'ai repris ma participation au concours. Désormais, je souhaite non seulement participer, mais aussi travailler dur pour améliorer la couleur.

Dans ma capacité, la stratégie pour augmenter le taux de réponse correcte du problème D d'ABC est bonne, donc je pense à inclure les questions passées pour le moment. Pendant ce temps, AtCoder ABC156 Problème D Bouquet Je l'ai essayé.

résultat

Quand j'ai lu le problème, j'ai tout de suite compris que le calcul lui-même était "Ah, je dois calculer le mod d'un grand nombre de combinaisons ordinales", mais il s'est avéré être "Comment dois-je faire?" Dans le calcul numérique que j'avais l'habitude de faire, les mods et les calculs d'entiers ne sortent pas.

Je ne réfléchirai pas dur pour moi tant que le niveau ne montera pas un peu, et je me référerai à la solution d'une personne qui semble excellente. Cliquez ici pour les soumissions de référence Soumission AtCoder # 10273434. Affectation

10273434.py


     1	import sys
     2	
     3	stdin = sys.stdin
     4	
     5	ns = lambda: stdin.readline().rstrip()
     6	ni = lambda: int(stdin.readline().rstrip())
     7	nm = lambda: map(int, stdin.readline().split())
     8	nl = lambda: list(map(int, stdin.readline().split()))
     9	
    10	n,a,b = nm()
    11	mod = 10**9 + 7
    12	s = pow(2,n,mod) - 1
    13	
    14	def fur(n,r):
    15	    p,q = 1,1
    16	    for i in range(r):
    17	        p = p*(n-i)%mod
    18	        q = q*(i+1)%mod
    19	    return p * pow(q,mod-2,mod) % mod
    20	
    21	print((s - fur(n,a) - fur(n,b)) % mod)
    22	

Le bleu qui essaie de jaunir à partir de 2020/03. Heure de soumission 21:09:30? .. .. C'est rapide. Le code est également simple. ..

Sachez qu'il existe une fonction pratique appelée pow (a, b, c). Python pow Si vous regardez cela, vous pouvez calculer jusqu'à l'élément inverse. Qui a soumis AtCoder # 10273434 Quand a et p sont premiers l'un par rapport à l'autre a ^ (p-2) = a ^ -1 (mod p) (Référence: théorème de Fermat). Comme vous pouvez le voir dans le lien Modifié dans la version 3.8: Pour les opérandes int, la forme à trois arguments de pow permet désormais au deuxième argument d'être négatif, permettant le calcul d'inverses modulaires. Les nombres négatifs sont autorisés dans le deuxième argument du pow à trois arguments depuis Python 3.8. Le Python d'AtCoder est de 3.4 au 12/03/2020, il semble donc que cette méthode soit utilisée.

À partir de la 14e ligne avec une fonction p = n * (n-1) * ... * (n-r+1) (mod) q = 1 * 2 * ... * r (mod) return p / q (mod) Comme C (n, r) = n! / (R! * (N-r)!) Est calculé.

plus tard Combinaison pour choisir n'importe quel nombre parmi n types de fleurs 2 ^ n Combinaison pour sélectionner un nombre parmi n types de fleurs C (n, a) Combinaison pour sélectionner un nombre parmi n types de fleurs C (n, b) n Combinaisons qui ne choisissent aucun des types de fleurs 1 alors 2^n - C(n,a) - C(n,a) -1 Est-ce fini avec? .. C'était facile de voir la réponse, mais cela n'a de sens que si je peux l'écrire moi-même. Je ne savais pas ce que représentait la fourrure.

J'ai essayé une autre soumission pour me demander pourquoi en C ++ Soumission AtCoder # 10266780. Le demandeur est jaune à compter du 14 mars 2020. Heure de soumission 21:03:23. Il semble que D soit soumis en premier, mais c'est toujours rapide. Affectation

10266780.cpp


     1	#include <bits/stdc++.h>
     2	using namespace std;
     3	typedef long long ll;
     4	#define all(x) (x).begin(),(x).end()
     5	const ll mod=1000000007,MAX=200005,INF=1<<30;
     6	
     7	ll inv[MAX],fac[MAX],finv[MAX];
     8	
     9	ll rui(ll a,ll b){
    10	    ll ans=1;
    11	    while(b>0){
    12	        if(b&1) ans=ans*a%mod;
    13	        a=a*a%mod;
    14	        b/=2;
    15	    }
    16	    return ans;
    17	}
    18	
    19	
    20	
    21	ll comb(ll a,ll b){
    22	    ll ans=1;
    23	    for(ll i=a;i>a-b;i--){
    24	        ans=ans*i%mod;
    25	    }
    26	    for(ll i=1;i<=b;i++){
    27	        ans=(ans*rui(i,mod-2))%mod;
    28	    }
    29	    return ans;
    30	}
    31	
    32	int main(){
    33	    
    34	    std::ifstream in("text.txt");
    35	    std::cin.rdbuf(in.rdbuf());
    36	    cin.tie(0);
    37	    ios::sync_with_stdio(false);
    38	    
    39	    //make();
    40	    
    41	    int N,A,B;cin>>N>>A>>B;
    42	    
    43	    cout<<(mod+mod+rui(2,N)-comb(N,A)-comb(N,B)-1)%mod<<endl;
    44	    
    45	}
    46	

run (a, b): une fonction qui calcule a ^ b (mod) comb (a, b): une fonction qui calcule C (a, b) (mod) Est défini par moi-même, et l'ensemble du processus ressemble à la soumission # 10273434. En regardant ce que j'ai fait, je me demande si C ++ n'a pas une fonction comme POW en Python du côté système.

Après tout, je n'ai pas écrit le code moi-même cette fois.

Recommended Posts

AtCoder ABC156 Problème D Calcul et séquence du module Bouquet, etc.
AtCoder ABC155 Problème D Pairs Review Note 2 NumPy et Python
AtCoder ABC155 Problème D Pairs Review Note 1
Problème de calcul avec le mod
Résolution avec Ruby et Python AtCoder ABC178 D Méthode de planification dynamique
Résolution avec Ruby et Python AtCoder ABC133 D Somme cumulée
AtCoder ABC151 Problème D Comparaison de la vitesse en C ++ / Python / PyPy
Résolution avec Ruby et Python AtCoder ABC138 D Liste adjacente
AtCoder ABC 182 Python (A ~ D)
Résolution en Ruby, Python et Java AtCoder ABC141 D Priority Queue
Résolution avec Ruby, Python et networkx AtCoder ABC168 D Liste adjacente
AtCoder ABC130 D Dichotomie de la somme cumulée résolue par Ruby et Python
AtCoder ABC 165 D Floor Function résolue en Ruby, Perl, Java et Python
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 131 D Tri des tableaux
Atcoder ABC60 D - Solution séparée de sac à dos simple
Mémo Atcoder débutant Python @ Keyence 2020, problème ABC
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Résoudre AtCoder ABC168 avec python (A ~ D)
Résoudre avec Ruby et Python AtCoder ABC084 D Somme cumulative des nombres premiers