[PYTHON] AtCoder Beginner Contest 110 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Ich fühle, dass die Leistung tatsächlich hellblau ist. Die Richtlinienänderung verlief gut. Ich habe das Gefühl, dass ich oft süchtig nach der Methode bin, für Probleme mit Brüchen unabhängig für jede Primzahl zu denken. Da ich die Primzahlbibliothek nicht organisiert habe, plane ich außerdem, in naher Zukunft häufig verwendete zu organisieren und zu veröffentlichen.

Problem A

Die Antwort ist, die größte Zahl mit 10 zu multiplizieren und die anderen so zu addieren, wie sie sind, aber ich habe sie als Zeichenfolge behandelt, ohne sie mit 10 zu multiplizieren.

answerA.py

abc=list(map(int,input().split()))
abc.sort(reverse=True)
print(int(str(abc[0])+str(abc[1]))+abc[2])

B-Problem

Es wäre gut, wenn es eine mögliche Sache bei Z gäbe, aber wir können sehen, dass es unten drei Bedingungen gibt. ・ $ X \ leqq Z \ leqq Y $ ・ $ Z> max (x_1, x_2,…, x_N) $ ・ $ Z \ leqq min (y_1, y_2,…, y_M) $ Finden Sie daher für Z = X ~ Y heraus, ob es etwas gibt, das $ max (x_1, x_2,…, x_N) <Z \ leqq min (y_1, y_2,…, y_M) $ ist. Sie können die for-Anweisung umdrehen, aber Sie können sie einfach mit einem beliebigen Operator schreiben. Außerdem ** habe ich die Ungleichung vergessen = = und es war 1WA **. Achtung.

answerB.py

n,m,x,y=map(int,input().split())
X=max(list(map(int,input().split())))
Y=min(list(map(int,input().split())))
for z in range(x+1,y+1):
    if X<z<=Y:
        print("No War")
        break
else:
    print("War")

answerB_better.py

n,m,x,y=map(int,input().split())
X=max(list(map(int,input().split())))
Y=min(list(map(int,input().split())))
print("No War" if any([X<z<=Y for z in range(x+1,y+1)]) else "War")

C-Problem

Wenn Sie sich auf die Buchstaben $ S_i, S_j, T_i, T_j $ zweier Indizes mit den Zeichenfolgen S und T konzentrieren, berücksichtigen Sie, dass $ S_i = T_i $ und $ S_j = T_j $ gelten. Angenommen, nur ** $ S_i = S_j $ gilt und unterscheidet sich für jedes der beiden anderen Zeichen **. Zu diesem Zeitpunkt besteht das Ziel darin, $ S_i = T_i $, $ S_j = T_j $ zu etablieren. Durch Ändern von $ S_i $ in $ T_i $ wird $ S_j $ jedoch auch zu $ T_i $ und $ S_j $. Da $ S_i $ durch die Operation zu $ T_j $ auch zu $ T_j $ wird, kann in diesem Fall S nicht mit T abgeglichen werden, es sei denn, ** $ T_i = T_j $ gilt auch **. Auch wenn ** $ T_i = T_j $ nur ** enthält, kann $ S_i $ in $ T_i $ geändert werden, aber $ S_i $ kann durch Ändern von $ S_j $ in $ S_i $ in $ T_j $ geändert werden. Da es sich in $ S_j $ ändert, kann S nicht mit T abgeglichen werden, es sei denn, ** $ S_i = S_j $ gilt auch **. Um dies zu verallgemeinern, müssen daher sowohl $ T_i = T_j $ als ** $ S_i = S_j $ als auch $ S_i = S_j $ ** als $ T_i = T_j $ gelten. .. Daher ist es ausreichend, die Indizes desselben Zeichens von S und T (vom Wörterbuch verwaltet) zu sammeln, und alle gesammelten Indizes sind gleich. Das heißt, in der ersten Stichprobe ist S "{" a ": [0]," z ": [1, 2]," e ": [3]," l ": [4] } `T wird {'a': [0], 'p': [1, 2], 'l': [3], 'e': [4]}`` Sie können sehen, dass die Kombination von ``[0], [1,2], [3], [4] gleich ist. Vergessen Sie auch nicht, zu sortieren, wenn Sie nur das Objekt aus der Karte extrahieren (da Sie den Schlüssel nicht benötigen) ** (dies war 1WA).

answerC.py

d,d_=dict(),dict()
s,t=input(),input()
l=len(s)
for i in range(l):
    if s[i] not in d:
        d[s[i]]=[i]
    else:
        d[s[i]].append(i)
for i in range(l):
    if t[i] not in d_:
        d_[t[i]]=[i]
    else:
        d_[t[i]].append(i)
x=[sorted(i[1]) for i in list(d.items())]
y=[sorted(i[1]) for i in list(d_.items())]
x.sort()
y.sort()
print("Yes" if x==y else "No")

D Problem

Da $ a_1, a_2,…, a_N $ ein Bruchteil von M ist, betrachten Sie zunächst die Kombination von Zahlen, die in $ a_1, a_2,…, a_N $ erscheinen, indem Sie Division usw. verwenden. Ich dachte, es wäre besser, es durch Teilen durch zu finden.

Zu diesem Zeitpunkt dachte ich, dass es möglich sein würde, dies effizient zu tun, indem man in aufsteigender oder absteigender Reihenfolge von Zahlen denkt, aber es wurde implementiert, da ** jede Zahl selbst keine Bedeutung hat ** (∵ einfach nach mehreren Möglichkeiten fragen). Ist ein wenig mühsam, also habe ich mir eine andere Methode überlegt.

Da hier $ a_1, a_2,…, a_N $ ein Bruchteil von M ist, wird $ durch Multiplikation der Primzahlen $ p_1, p_2,…, p_k $ berechnet, die auftreten, wenn ** M faktorisiert wird. Mir ist aufgefallen, dass a_1, a_2,… und a_N $ jeweils ausgedrückt werden können **. Mit anderen Worten, schreiben Sie die folgende Tabelle und definieren Sie $ a_i $ ($ i $ = 1 ~ $ N ). ( M = p_1 ^ {q_1} p_2 ^ {q_2}… p_k ^ {q_k} $)

Wenn die Nummer von $ p_j $ ($ j $ = 1 ~ $ k $) $ a_1, a_2,…, a_N $ zugewiesen wird, kann dies auch als eine andere Nummernfolge angesehen werden, sodass jedes $ p_j $ ($ j $ =) Überlegen Sie, wie viele Kombinationen von Zuordnungen von 1 ~ $ k $) zu $ a_1, a_2,…, a_N $ und denken Sie über die Multiplikation nach (** Jedes $ p_j $ ($ j $ = 1 ~) Man kann sagen, dass die Kombination von $ k $) unabhängig bestimmt wird **.).

Auch für die Kombination der Zuordnung von $ p_j $ zu $ a_1, a_2,…, a_N $ ist es ausreichend, $ N-1 $ Partitionen und $ q_j $ Bälle zu berücksichtigen und zu überlegen, wie die Bälle und Partitionen angeordnet werden. $ \ frac {(N-1 + q_j)!} {(N-1)! \ times q_j!} = _ {N-1 + q_j} C _ {N-1} $ Das stimmt (in der Mathematik der High School) Da es Wissen ist, werde ich die Erklärung weglassen.)

Außerdem ist $ q_j $ deutlich kleiner als 30 (∵ $ 10 ^ 9 <2 ^ {30} $), also $ N-1 + q_j <10 ^ 6 , und die Kombinationsberechnungstabelle ist O ( N ). Sie können auch mit der Methode zum Initialisieren mit) und Durchführen der Kombinationsberechnung mit O (1) auskommen (für die Kombinationsberechnung [Kenchons Artikel](https://drken1215.hatenablog.com/entry/2018/06)). / 08/210000).). Daher kann die Berechnung der Anzahl der Sequenzen mit O ( k $) durchgeführt werden, und da k deutlich kleiner als 30 ist (∵ $ 10 ^ 9 <2 ^ {30} $), ist die Primfaktorisierung durch die Prime_factorize-Funktion O ( Sie können dieses Problem mit O (max (N, $ \ sqrt {M} $)) lösen, zusätzlich zu $ \ sqrt {M} $).

Ab ✳︎ Hauptsatz ist die Primzahl kleiner als x Es scheint sich um $ \ frac {x} {\ log {x}} $ zu handeln. In diesem Fall handelt es sich um $ \ frac {x} {\ log {x}} \ fallenddotseq = 4,8 \ mal 10 ^ 7 $ von $ x = 10 ^ 9 $. Der tatsächliche Wert beträgt $ 5.0847534 \ times 10 ^ 7 $, sodass Sie sehen können, dass dies eine ziemlich gute Annäherung ist. (** Wenn ich Zeit habe, möchte ich eine bessere Formel für diese Annäherung erstellen. **)

✳︎ Der Grund, warum die Implementierung von Prime_factorize schmutzig ist, ist, dass ich sie geschrieben habe, als ich mir das Spiralbuch angesehen habe, als ich den Wettbewerb Pro gestartet habe. In naher Zukunft möchte ich einen Artikel mit einer schönen Implementierung hochladen.

answerD.cc

#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXRR 1000 //√ Stellen Sie eine Zahl größer oder gleich MAXR ein
#define MAXR 200000

ll fac[MAXR], finv[MAXR], inv[MAXR];

//Vorbehandlung, um einen Tisch zu machen
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAXR; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Berechnung des Binärkoeffizienten
ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void Prime_factorize(vector<ll>& v,ll n){
    if(n<=1) return;
    ll l=ll(sqrt(n));
    for(ll i=2;i<l+1;i++){
        if(n%i==0){
            Prime_factorize(v,i);Prime_factorize(v,ll(n/i));return;
        }
    }
    v.push_back(n);return;
}

signed main(){
    COMinit();
    map<ll,ll> ma;
    ll n,m;cin >> n >> m;
    vector<ll> vp;
    Prime_factorize(vp,m);
    REP(i,SIZE(vp)){
        ma[vp[i]]++;
    }
    ll ans=1;
    for(auto i=ma.begin();i!=ma.end();i++){
        ans*=COM(i->S+(n-1),n-1);
        ans%=MOD;
    }
    cout << ans << endl;
}