AtCoder Beginner Contest 110 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-25 11.27.48.png

Impressions

Je sens que la performance est en fait bleu clair. Le changement de politique s'est bien passé. Je sens que je suis souvent accro à la méthode de ** penser indépendamment pour chaque nombre premier ** pour les problèmes liés aux fractions. De plus, comme je n'ai pas organisé la bibliothèque de nombres premiers, je prévois d'organiser et de publier celles fréquemment utilisées dans un proche avenir.

Problème A

La réponse est de multiplier le plus grand nombre par 10 et d'ajouter les autres tels quels, mais je l'ai traité comme une chaîne de caractères sans multiplier par 10.

answerA.py


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

Problème B

Ce serait bien s'il y avait une chose possible à propos de Z, mais nous pouvons voir qu'il y a trois conditions ci-dessous. ・ $ X \ leqq Z \ leqq Y $ ・ $ Z> max (x_1, x_2,…, x_N) $ ・ $ Z \ leqq min (y_1, y_2,…, y_M) $ Par conséquent, pour Z = X ~ Y, cherchez s'il y a quelque chose qui est $ max (x_1, x_2,…, x_N) <Z \ leqq min (y_1, y_2,…, y_M) $. Vous pouvez activer l'instruction for, mais vous pouvez facilement l'écrire à l'aide de l'opérateur any. Aussi, ** j'ai oublié le nombre inégal = et c'était 1WA **. Faites attention.

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")

Problème C

En nous concentrant sur les lettres $ S_i, S_j, T_i, T_j $ de deux index avec les chaînes S et T, considérons que $ S_i = T_i $ et $ S_j = T_j $ tiennent. Disons que seul ** $ S_i = S_j $ tient et est différent pour l'un des deux autres caractères **. À ce stade, l'objectif est de maintenir $ S_i = T_i $, $ S_j = T_j $, mais en changeant $ S_i $, en $ T_i $, $ S_j $ devient également $ T_i $, et $ S_j $, Puisque $ S_i $ devient également $ T_j $ par l'opération pour faire $ T_j $, dans ce cas, S ne peut pas être mis en correspondance avec T à moins que ** $ T_i = T_j $ soit également validé **. De plus, même lorsque ** $ T_i = T_j $ contient seulement **, $ S_i $ peut être changé en $ T_i $, mais $ S_i $ peut être changé en $ T_j $ en changeant $ S_j $, en $ S_i $. Puisqu'il devient $ S_j $, S ne peut pas être mis en correspondance avec T à moins que ** $ S_i = S_j $ soit également validé **. Par conséquent, pour généraliser cela, à la fois $ T_i = T_j $ quand ** $ S_i = S_j $ et $ S_i = S_j $ ** quand $ T_i = T_j $ doivent tenir. .. Il suffit donc de collecter les index du même caractère par S et T (gérés par le dictionnaire), et tous les index collectés sont les mêmes. Autrement dit, dans le premier exemple, S est {'a': [0], 'z': [1, 2], 'e': [3], 'l': [4] } `T devient{'a': [0], 'p': [1, 2], 'l': [3], 'e': [4]} Vous pouvez voir que la combinaison de [0], [1,2], [3], [4] '' est égale. N'oubliez pas non plus de s ** ort lorsque vous récupérez uniquement l'élément de la carte (puisque vous n'avez pas besoin de la clé) ** (c'était 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")

Problème D

Tout d'abord, puisque $ a_1, a_2,…, a_N $ est une fraction de M, considérons la combinaison des nombres qui apparaissent dans $ a_1, a_2,…, a_N $ en utilisant la division, etc., puis arrangez-les dans l'ordre (duplication). J'ai pensé qu'il valait mieux le trouver en divisant par).

À ce moment, je pensais qu'il serait possible de le faire efficacement en pensant par ordre croissant ou décroissant des nombres, mais cela a été implémenté car ** chaque nombre lui-même n'a pas de signification ** (∵ demandez simplement plusieurs façons). C'est un peu gênant, alors j'ai pensé à une autre méthode.

Ici, puisque $ a_1, a_2,…, a_N $ est une fraction de M, $ est calculé en multipliant les nombres premiers $ p_1, p_2,…, p_k $ qui apparaissent lorsque ** M est factorisé. J'ai remarqué que a_1, a_2,… et a_N $ peuvent être exprimés ** respectivement. En d'autres termes, envisagez d'écrire le tableau suivant et de définir respectivement $ a_i $ ($ i $ = 1 ~ $ N ). ( M = p_1 ^ {q_1} p_2 ^ {q_2}… p_k ^ {q_k} $)

a_1 a_2 a_N sum
$ p_1 $ 0~q_1 0~q_1 0~q_1 q_1
$ p_2 $ 0~q_2 0~q_2 0~q_2 q_2
$ p_k $ 0~q_k 0~q_k 0~q_k q_k

Aussi, si le nombre de $ p_j $ ($ j $ = 1 ~ $ k $) est assigné à $ a_1, a_2,…, a_N $, il peut être considéré comme une séquence de nombres différente, donc chaque $ p_j $ ($ j $ =) Considérez combien de combinaisons d'allocations de 1 ~ $ k $) à $ a_1, a_2,…, a_N $ peuvent être considérées pour la multiplication (** Chaque $ p_j $ ($ j $ = 1 ~) On peut dire que la combinaison de $ k $) est déterminée indépendamment **.).

Aussi, comme pour la combinaison d'allocation de $ p_j $ à $ a_1, a_2,…, a_N $, il suffit de considérer les partitions $ N-1 $ et les balles $ q_j $ et de considérer comment organiser les boules et les partitions. $ \ frac {(N-1 + q_j)!} {(N-1)! \ times q_j!} = _ {N-1 + q_j} C _ {N-1} $ C'est vrai (en mathématiques au lycée) Puisqu'il s'agit de connaissances, j'omettrai l'explication.)

De plus, puisque $ q_j $ est clairement inférieur à 30 (∵ $ 10 ^ 9 <2 ^ {30} $), $ N-1 + q_j <10 ^ 6 , et la table de calcul des combinaisons est O ( N ). Vous pouvez également vous contenter de la méthode d'initialisation avec) et d'effectuer le calcul de combinaison avec O (1) (Pour le calcul de combinaison, [article de Kenchon](https://drken1215.hatenablog.com/entry/2018/06) / 08/210000).). Par conséquent, le calcul du nombre de séquences peut être fait avec O ( k $), et k est clairement inférieur à 30 (∵ $ 10 ^ 9 <2 ^ {30} $), donc la factorisation première par la fonction Prime_factorize est O ( Vous pouvez résoudre ce problème avec O (max (N, $ \ sqrt {M} $)) en plus d'être $ \ sqrt {M} $).

D'après ✳︎ Théorème premier, le nombre premier est inférieur à x Il semble qu'il s'agisse de $ \ frac {x} {\ log {x}} $. Dans ce cas, il s'agira de $ \ frac {x} {\ log {x}} \ Fallingdotseq = 4.8 \ times 10 ^ 7 $ de $ x = 10 ^ 9 $. La valeur réelle est de 5,0847534 $ \ fois 10 ^ 7 $, donc vous pouvez voir que c'est une assez bonne approximation. (** Si j'ai le temps, j'aimerais faire une meilleure formule pour cette approximation. **)

✳︎ La raison pour laquelle l'implémentation de Prime_factorize est sale est que je l'ai écrite en regardant le livre en spirale lorsque j'ai commencé le concours pro. Dans un proche avenir, j'aimerais télécharger un article avec une belle mise en œuvre.

answerD.cc


#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
#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() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXRR 1000 //√ Définissez un nombre supérieur ou égal à MAXR
#define MAXR 200000

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

//Prétraitement pour faire une table
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;
    }
}

//Calcul du coefficient binaire
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;
}

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes