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.
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é.
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