AtCoder ABC156 Problem D Ich habe Bouquet ausprobiert. Anordnung der Mod-Inverse-Element- und Mod-Ordnungskombinationsberechnung.
Ich war eine Weile so beschäftigt mit der Arbeit, dass ich enttäuscht war, dass ich nicht einmal am Wettbewerb teilnehmen konnte, aber da ich mich niedergelassen hatte, nahm ich wieder am Wettbewerb teil. Von nun an möchte ich nicht nur teilnehmen, sondern auch hart daran arbeiten, die Farbe zu verbessern.
Meiner Meinung nach ist die Strategie, die richtige Antwortrate für das D-Problem von ABC zu erhöhen, gut, daher denke ich vorerst darüber nach, frühere Fragen einzubeziehen. In der Zwischenzeit AtCoder ABC156 Problem D Bouquet Ich habe es versucht.
Als ich das Problem las, verstand ich sofort, dass die Berechnung selbst "Ah, ich muss den Mod einer großen Anzahl von Ordnungskombinationen berechnen", aber es stellte sich heraus, dass "Wie mache ich das?" In der numerischen Berechnung, die ich früher durchgeführt habe, kommen Mods und Integer-Berechnungen nicht heraus.
Ich werde hart für mich selbst nachdenken, nachdem ich ein etwas höheres Niveau erreicht habe, und ich werde mich auf die Lösung einer Person beziehen, die ausgezeichnet zu sein scheint. Klicken Sie hier für Referenzbeiträge AtCoder-Einreichung Nr. 10273434. Posting
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
Der Blaue, der ab 2020/03 versucht, gelb zu werden. Einreichungszeit 21:09:30? .. .. Es ist schnell. Der Code ist auch einfach. ..
Wisse, dass es eine praktische Funktion gibt, die pow (a, b, c) genannt wird. Python pow Wenn Sie sich das ansehen, können Sie bis zum umgekehrten Element berechnen. Wer hat AtCoder # 10273434 eingereicht? Wenn a und p zueinander prim sind, ist a ^ (p-2) = a ^ -1 (mod p) (Referenz: Satz von Fermat). Wie Sie im Link sehen können In Version 3.8 geändert: Für int-Operanden ermöglicht die Drei-Argument-Form von pow nun, dass das zweite Argument negativ ist, was die Berechnung modularer Inversen ermöglicht. Negative Zahlen sind im zweiten Argument des Pow mit drei Argumenten seit Python 3.8 zulässig. AtCoders Python ist ab dem 12.03.2020 3.4, daher scheint diese Methode verwendet zu werden.
Ab der 14. Zeile mit einer Funktion p = n * (n-1) * ... * (n-r+1) (mod) q = 1 * 2 * ... * r (mod) return p / q (mod) Als C (n, r) = n! / (R! * (N-r)!) Wird berechnet.
später Kombination zur Auswahl einer beliebigen Anzahl aus n Arten von Blumen 2 ^ n Kombination zur Auswahl einer Zahl aus n Arten von Blumen C (n, a) Kombination zur Auswahl einer Zahl aus n Arten von Blumen C (n, b) n Kombinationen, bei denen keine der Blumentypen ausgewählt wird 1 damit 2^n - C(n,a) - C(n,a) -1 Ist es fertig mit? .. Es war leicht, die Antwort zu sehen, aber es macht keinen Sinn, wenn ich sie nicht selbst schreiben kann. Ich wusste nicht, wofür Fell steht.
Ich habe eine andere Vorlage versucht, um mich zu fragen, warum in C ++ AtCoder-Einreichung Nr. 10266780. Der Einreicher ist ab dem 14. März 2020 gelb. Einreichungszeit 21:03:23. Es scheint, dass D zuerst eingereicht wird, aber es ist immer noch schnell. Posting
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): Eine Funktion, die a ^ b (mod) berechnet Kamm (a, b): Eine Funktion, die C (a, b) berechnet (mod) Wird von mir selbst definiert und der gesamte Prozess sieht genauso aus wie die Einreichung # 10273434. Wenn ich mir anschaue, was ich gemacht habe, frage ich mich, ob C ++ auf der Systemseite keine Funktion wie POW in Python hat.
Immerhin habe ich den Code diesmal nicht selbst geschrieben.
Recommended Posts