AtCoder ABC156 Problem D I tried Bouquet. Arrangement of mod inverse element and mod permutation combination calculation.
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.
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