Les résultats de cette fois

Impressions de cette époque

Je ne suis pas doué pour résoudre rapidement, mais je pense qu'il a fait du bon travail. Je veux pouvoir passer le problème F à temps. Je veux pouvoir penser logiquement avec une marge même si la considération devient compliquée. Pour cela, je pense que je devrais écrire le mémo un peu plus joliment. J'ai récemment révisé le concours, alors j'aimerais moi-même évaluer ce point. J'espère que les résultats se concrétiseront bientôt.

Problème A

Qu'elle soit en majuscule ou non peut être déterminée par la fonction isupper, et c'est comme suit.

`A.py`


a=input()
print("A" if a.isupper() else "a")

Problème B

Je pense que le problème de ce modèle apparaît dans AtCoder. Puisque K sont sélectionnés par ordre croissant de montant, vous pouvez les trier par ordre croissant et considérer la somme du 1er au Kth du tableau.

`B.py`


n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
print(sum(p[:k]))

Problème C

Comme prévu la dernière fois, vous pouvez voir que nous essayons de faire une falaise avec C. Je pense que le processus est gênant, mais je suis étonné qu'un nombre considérable de personnes passent.

Premièrement, si la longueur du nom du chien est $ l $, il est clair qu'il existe 26 $ ^ l $ façons de nommer le chien. De plus, à partir de là, vous pouvez voir qu'il est pratique de le considérer comme un nombre 26-aire. ** Si vous décidez de la longueur du nom, vous pouvez le considérer comme le processus de détermination des chiffres n-aires **, j'ai donc décidé de trouver d'abord la longueur du nom avec la fonction n_len.

Ici, la longueur du nom peut être obtenue en soustrayant $ 26,26 ^ 2,… $ du N donné afin qu'il ne devienne pas 0 ou moins, donc dans ce processus ** Longueur du nom Il a l'information $ l $ ** et le nombre $ N $ ** dans le nom de cette longueur (dans l'ordre lexical).

Si vous pensez que le traitement du nombre 26-aire est décidé à partir du chiffre inférieur, vous pouvez trouver l'alphabet de ce chiffre avec n% 26 et supprimer ce chiffre avec n // = 26, alors nommez ceci Tout ce que vous avez à faire est la longueur $ l $.

`C.py`


n=int(input())-1
def n_len():
    global n
    i=1
    while n>=26**i:
        n-=26**i
        i+=1
    return i
l=n_len()
alp=[chr(i) for i in range(97, 97+26)]
ans=""
for i in range(l):
    k=n%26
    ans=alp[k]+ans
    n//=26
print(ans)

Problème D

Si vous enregistrez la colonne numérique en tant que tableau et effectuez un calcul de requête, vous devez vérifier tous les éléments du tableau et le montant du calcul sera de $ O (QN) $, ce qui est trop tard.

Le traitement de la requête consiste à réécrire tous les nombres avec la valeur $ B_i $ en $ C_i $, et si vous enregistrez le nombre de chaque nombre dans la colonne numérique du dictionnaire, ce traitement est $ O (1) $ Tu peux le faire.

Par conséquent, si vous préparez une variable pour enregistrer la somme des éléments et considérez la possibilité que $ B_i et C_i $ n'existent pas dans la séquence, vous pouvez implémenter un programme avec un montant de calcul de $ O (Q) $. Je peux le faire.

`D.py`


n=int(input())
a=dict()
ans=0
for i in map(int,input().split()):
    ans+=i
    if i in a:
        a[i]+=1
    else:
        a[i]=1
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    if c not in a:
        a[c]=0
    if b not in a:
        a[b]=0
    ans=ans-b*a[b]+c*a[b]
    a[c]+=a[b]
    a[b]=0
    print(ans)

E problème

Comme vous pouvez le voir dans l'article de hamayanhamayan, il existe trois propriétés fréquemment utilisées de XOR ($ a). $ Est un entier supérieur ou égal à 0).

1: Loi de change et loi de connexion 2:$a \oplus a=0$ 3:$2a \oplus (2a+1)=1 \leftrightarrow 4a \oplus (4a+1) \oplus (4a+2) \oplus (4a+3)=0$

En plus de cela, un entier considérant l'espace vectoriel $ F ^ n $ tel que $ F = \ {0,1 \} $, (nombre de bits) = $ n $ et $ \ oplus $ comme une connexion linéaire. Il y a aussi un problème (AGC045 Un problème) qui exprime et juge l'indépendance linéaire et la dépendance linéaire, mais pour plus de détails, M. hamayanhamayan Veuillez vous référer à l'article etc.

Dans ce problème, nous utilisons principalement la propriété 2 ci-dessus et considérons qu'elle peut être effacée avec une bonne sensation car elle vaut 0 quand une couverture se produit **, et elle devient comme le montre la figure ci-dessous. (Utilisez également implicitement la propriété 1.)

En considérant le XOR de $ a_1, a_2,…, a_n $, il est clair que $ b_1, b_2,…, b_n $ apparaissent $ n-1 $ à chaque fois. De plus, concentrez-vous sur $ a_i $ pour trouver ** $ b_i $ ** et XOR $ a_i $ à nouveau pour obtenir $ b_1,…, b_ {i-1}, b_ {i + 1} Vous pouvez voir que,…, b_n $ apparaît $ n $ fois chacun, et $ b_i $ apparaît $ n-1 $ fois chacun. Par conséquent, en raison de la contrainte du problème, $ n $ est pair, donc tous les XOR de $ b_1,…, b_ {i-1}, b_ {i + 1},…, b_n $ valent 0, et il ne reste que $ b_i $. Je comprends.

À partir de ce qui précède, trouvez le XOR de $ a_1, a_2,…, a_n $ comme un pré-calcul, et trouvez le nombre et le XOR de chacun de $ a_1, a_2,…, a_n $ comme réponse. ..

`E.py`


n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    b^=a[i]
ans=[0]*n
for i in range(n):
    ans[i]=a[i]^b
print(" ".join(map(str,ans)))

Problème F

Cela semblait être résolu avec un peu plus de torsion de la tête ... Blue diff a de nombreux problèmes comme celui-ci ...

(Ci-après, la chaîne de caractères d'origine est exprimée en $ S $, sa longueur est exprimée en $ N $, le caractère $ i $ est exprimé en $ S_i $ et la chaîne de caractères finalement générée est exprimée en $ S ^ {'} $. )

Tout d'abord, j'ai douté de DP car il s'agit ** d'une chaîne de caractères et l'ordre semble être lié **, mais ce n'est clairement pas à temps pour le calcul. Ici, comme il semble que de nombreuses chaînes de caractères puissent être représentées en raison de l'expérience utilisant l'échantillon et de la limitation du problème, j'ai pensé que ** je voudrais le garder dans environ $ O (K + N) $ par calcul de combinaison **. De plus, comme le degré de liberté des caractères à ajouter plus tard est élevé, nous avons adopté la méthode pour décider de l'emplacement des caractères inclus dans ** $ S $, puis en considérant le nombre total de combinaisons de caractères à ajouter ultérieurement **.

Cependant, si vous décidez des caractères à inclure dans $ S $ et que vous demandez ensuite la combinaison en supposant qu'il y a 26 autres caractères chacun, il y a une possibilité qu'une chaîne de caractères en double se produise dans ** $ S ^ {'} $ **. .. Par conséquent, si vous le combinez avec la politique de décision de la position des caractères inclus dans $ S $, il semble que la façon de faire $ S ^ {'} $ soit uniquement décidée en fonction de la position des caractères inclus dans ** $ S $. Demandez simplement la méthode **. En d'autres termes, cette méthode peut être reformulée en trouvant une méthode ** (✳︎) qui détermine de manière unique la position des caractères contenus dans $ S $ pour ** $ S ^ {'} $.

(↑ ** La réponse est uniquement déterminée par une certaine méthode Comptage $ \ leftrightarrow $ Une certaine méthode est uniquement déterminée à partir de ce qui est compté **. Il y a beaucoup de problèmes avec le thème de l'unicité, donc je veux être en mesure de le résoudre. est.)

Ici, en ce qui concerne (it), il peut être déterminé de manière unique si c'est ** la position où le caractère contenu dans $ S $ apparaît en premier en regardant $ S ^ {'} $ de face **. Je vais. Aussi, sous ceci, de la position de $ S \ _ {i-1} $ de $ S ^ {'} $ à la position de $ S \ _ {i} $ ** $ S \ _ {i} $ Vous pouvez utiliser tous les alphabets ** sauf. Par conséquent, il y a 25 (= 26-1) caractères qui ne sont pas inclus dans $ S $ avant la position de $ S \ _ {N} $. Aussi, pour la chaîne de caractères après la position de $ S \ _ {N} $, n'importe quel alphabet peut être utilisé, il y a donc 26 façons.

De ce qui précède, si vous décidez de la position de $ S \ _ {N} $, qui est la limite entre le cas de 26 voies et le cas de 25 voies, 26 et 25 vous indiqueront combien de positions de caractères sont incluses dans le $ S $ restant. L'implémentation suivante peut être obtenue en trouvant le nombre de puissances. De plus, ce qui suit utilise la structure modint qui gère toujours les entiers par modding.

`F.cc`


//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x est un conteneur tel que vector
#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
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 3000000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

template<ll mod> class modint{
public:
    ll val=0;
    //constructeur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Copier le constructeur
    modint(const modint &r){val=r.val;}
    //Opérateur arithmétique
    modint operator -(){return modint(-val);} //unaire
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Opérateur d'assignation
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //Opérateur de comparaison d'équivalence
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Puissance
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}

//Calcul du coefficient binomial
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Créer une table
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}
//Partie calcul
mint 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];
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll k,l;cin>>k;
    string s;cin>>s;n=SIZE(s);
    mint ans=0;
    FOR(i,n,k+n){
        ans+=(modpow(25,i-n)*modpow(26,k+n-i)*COM(i-1,n-1));
    }
    cout<<ans<<endl;
}

[PYTHON] AtCoder Débutant Contest 171 Critique