AtCoder ABC156 Problem D Bouquet mod calculation and permutations, etc.

Overview

AtCoder ABC156 Problem D I tried Bouquet. Arrangement of mod inverse element and mod permutation combination calculation.

Background

I was so busy with work for a while that I was disappointed that I couldn't even participate in the contest, but since I had settled down, I resumed participating in the contest. From now on, I would like to not only participate but also work hard to improve the color.

In my ability, the strategy to raise the correct answer rate of ABC's D problem is good, so I am thinking of including past questions for the time being. Meanwhile, AtCoder ABC156 Problem D Bouquet I tried it.

result

When I read the problem, I immediately understood that the calculation itself was "Ah, I have to calculate the mod of a large number of permutation combinations", but it turned out to be "How do I do it?" In the numerical calculation that I used to do, mods and integer calculations do not come out.

I will think hard for myself after I get a little higher level, and I will refer to the solution of a person who seems to be excellent. Click here for reference submissions AtCoder submission # 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	

The blue one who is trying to turn yellow as of 2020/03. Submission time 21:09:30? .. .. It's fast. The code is also simple. ..

Know that there is a convenient function called pow (a, b, c). Python pow If you look at this, you can calculate up to the inverse element. For submitters of AtCoder Submission # 10273434 When a and p are relatively prime a ^ (p-2) = a ^ -1 (mod p) It seems that the principle of is used (Reference: Fermat's Little Theorem). As you can see in the link Changed in version 3.8: For int operands, the three-argument form of pow now allows the second argument to be negative, permitting computation of modular inverses. Negative numbers are allowed in the second argument of the three-argument pow since Python 3.8. AtCoder's Python is 3.4 as of 03/12/2020, so it seems that you are using this method.

From the 14th line with a function p = n * (n-1) * ... * (n-r+1) (mod) q = 1 * 2 * ... * r (mod) return p / q (mod) As C (n, r) = n! / (R! * (N-r)!) Is calculated.

later A combination of n choices of any number of flowers from 2 ^ n Combination to select a number from n kinds of flowers C (n, a) Combination to select a number from n kinds of flowers C (n, b) n Combinations that do not choose any of the types of flowers 1 so 2^n - C(n,a) - C(n,a) -1 Is it finished with? .. It's easy to see the answer, but it doesn't make sense unless you can write it yourself. I didn't know what fur stands for.

I tried another submission to wonder why in C ++ Submit AtCoder # 10266780. The submitter is yellow as of March 14, 2020. Submission time 21:03:23. It seems that D is submitted first, but it's still fast. 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): function to calculate a ^ b (mod) comb (a, b): A function that calculates C (a, b) (mod) Is defined by myself, and the whole process looks the same as submission # 10273434. Looking at what I made, I wonder if Python's POW-like functions are not prepared on the system side in C ++.

After all, I didn't write the code myself this time.

Recommended Posts

AtCoder ABC156 Problem D Bouquet mod calculation and permutations, etc.
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
AtCoder ABC155 Problem D Pairs Review Note 1
Calculation problem using mod
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
AtCoder ABC 182 Python (A ~ D)
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Atcoder ABC60 D --Simple Knapsack Separate Solution
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers