This time's results

Impressions of this time

I'm not good at solving quickly, but I think he's done a good job. I want to be able to pass the F problem in time. I want to be able to think logically with a margin even if the consideration becomes complicated. For that purpose, I think I should write the memo a little more beautifully. I've been reviewing the contest recently, so I'd like to evaluate that point myself. I hope that the results will come to fruition soon.

Problem A

Whether it is uppercase or not can be determined by the isupper function, and it is as follows.

`A.py`


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

B problem

I feel that the problem of this pattern is appearing in AtCoder. Since K are selected in ascending order of amount, you can sort in ascending order and consider the sum of 1st to Kth of the array.

`B.py`


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

C problem

As expected last time, you can see that we are trying to make a cliff with C. I think the process is troublesome, but I'm surprised that a considerable number of people are passing through.

First, if the length of the dog's name is $ l $, it is clear that there are $ 26 ^ l $ ways to name the dog. Also, from here you can see that it is convenient to think of it as a 26-ary number. ** If you decide the length of the name, you can think of it as the process of determining the n-ary digits **, so I decided to find the length of the name with the n_len function first.

Here, the length of the name can be obtained by subtracting $ 26,26 ^ 2,… $ from the given N so that it does not become 0 or less, so under this process ** the length of the name It has the information $ l $ ** and the number $ N $ ** in the name of that length (in lexicographical order).

Considering that the processing of the 26-ary number is decided from the lower digit, the alphabet of that digit can be obtained by n% 26 and the digit can be discarded by n // = 26. All you have to do is for the length $ l $ of.

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

D problem

If you save the sequence as an array and perform query calculation, you need to check all the elements of the array, and the amount of calculation will be $ O (QN) $, which is too late.

The query processing is to rewrite all the numbers with the value $ B_i $ to $ C_i $, and if you save the number of each number in the sequence in the dictionary, this processing will be $ O (1) $. You can do it.

Therefore, if you prepare a variable to save the sum of elements and consider the possibility that $ B_i and C_i $ do not exist in the sequence, you can implement a program with a computational complexity of $ O (Q) $. I can do it.

`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 problem

As you can see from hamayanhamayan's article, there are three commonly used properties of XOR ($ a). $ Is an integer greater than or equal to 0).

1: Exchange law and associative law 2:$a \oplus a=0$ 3:$2a \oplus (2a+1)=1 \leftrightarrow 4a \oplus (4a+1) \oplus (4a+2) \oplus (4a+3)=0$

In addition to this, an integer considering the vector space $ F ^ n $ such that $ F = \ {0,1 \} $, (number of bits) = $ n $ and $ \ oplus $ as a linear combination. There is also a problem (AGC045 A problem) that expresses and judges linear independence and linear dependence, but for details, hamayanhamayan mentioned earlier. Please refer to the article etc.

In this problem, we mainly use the above property 2 and consider that it can be erased with a good feeling because it is 0 when a cover occurs **, and it becomes as shown in the figure below. (Implicitly use property 1 as well.)

Considering the XOR of $ a_1, a_2,…, a_n $, it is clear that $ b_1, b_2,…, b_n $ appear $ n-1 $ each time. In addition, focus on $ a_i $ to find ** $ b_i $ ** and XOR $ a_i $ again to $ b_1,…, b_ {i-1}, b_ {i + 1} You can see that ,…, b_n $ appears $ n $ times each, and $ b_i $ appears $ n-1 $ times each. Therefore, because $ n $ is an even number due to the constraint of the problem, the XOR by $ b_1,…, b_ {i-1}, b_ {i + 1},…, b_n $ is all 0, and only $ b_i $ remains. I understand.

From the above, find the XOR of $ a_1, a_2,…, a_n $ as the pre-calculation, and find the number and the XOR of each of $ a_1, a_2,…, a_n $ as the answer. ..

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

F problem

It seemed to be solved with a little more twist of my head ... Blue diff has many problems like this ...

(Hereafter, the original string is $ S $, its length is $ N $, the $ i $ character is $ S_i $, and the final string is $ S ^ {'} $. )

First of all, I doubted DP because it is ** a character string and the order seems to be related **, but it is clearly not in time for computational complexity. Here, since it seems that many character strings can be represented due to the experiment using the sample and the constraints of the problem, I thought that ** I would like to keep it in about $ O (K + N) $ by combination calculation **. Also, since the degree of freedom of characters to be added later is high, we adopted the method of deciding the location of the characters included in ** $ S $ and then considering the total number of combinations of characters to be added later **.

However, if you decide the characters to be included in $ S $ and then ask for the combination assuming that there are 26 other characters each, there is a possibility that a duplicate character string will occur in ** $ S ^ {'} $ **. .. Therefore, if you combine it with the policy of determining the position of the characters included in $ S $, it seems that how to make $ S ^ {'} $ is uniquely determined based on the position of the characters included in ** $ S $. Just ask for the method **. In other words, this method can be rephrased by finding a method ** (✳︎) that uniquely determines the position of the characters contained in $ S $ with respect to ** $ S ^ {'} $.

(↑ ** The answer is uniquely determined by a certain method Counting $ \ leftrightarrow $ A certain method is uniquely determined from what is counted **. There are many problems with the theme of uniqueness, so I want to be able to solve it. is.)

Here, regarding (✳︎), it can be uniquely determined if it is ** the position where the character contained in $ S $ first appears when looking at $ S ^ {'} $ from the front **. I will. Also, under this, from the position of $ S \ _ {i-1} $ of $ S ^ {'} $ to the position of $ S \ _ {i} $ ** $ S \ _ {i} $ You can use all but the alphabet **. Therefore, there are 25 (= 26-1) characters that are not included in $ S $ before the position of $ S \ _ {N} $. Also, for the character string after the position of $ S \ _ {N} $, any alphabet can be used, so there are 26 ways.

From the above, if you decide the position of $ S \ _ {N} $, which is the boundary between 26 cases and 25 ways, 26 and 25 will tell you how many character positions are included in the remaining $ S $. The implementation is as follows by finding the number of powers. In addition, the following uses the modint structure that always manages integers by mod.

`F.cc`


//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array

using namespace std;
typedef long long ll;

//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ll(x.size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 3000000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

template<ll mod> class modint{
public:
    ll val=0;
    //constructor
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Copy constructor
    modint(const modint &r){val=r.val;}
    //Arithmetic operator
    modint operator -(){return modint(-val);} //unary
    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;}
    //Assignment operator
    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;
    }
    //Equivalence comparison operator
    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>;

//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to x
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Exponentiation
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;
}

//Calculation of binomial coefficient
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Creating a 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];
    }
}
//Calculation part
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 for speeding up input
    //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 Beginner Contest 171 Review