Professor Calculus was working with the government on an important project. The aim of the project was to make a shark submarine which would help the government to work in the areas which were highly dominated by the sharks. The enemies got to know about it and they had kidnapped Professor Calculus.
image source: google
The government is searching for him and has also informed Tintin and detectives (Thomson and Thompson). Tintin and Snowy are preparing to search for Professor Calculus. Tintin has also informed everything to Captain Haddock and his first response is - “Blistering Barnacles”. They all are set to pay a visit to different cities to search for Professor. They can only do two things while paying visits to different cities:
Search for Professor
Take Rest
image source: google
A visit can be of a single or multiple days. During a visit, they cannot take rest for two days consecutively. Tintin has selected a range of minimum (M) and maximum (X) number of days required to search for the Professor. Tintin wants to select V different visits between the minimum and the maximum number of days (both inclusive). The only condition is that the visits should be of the same duration (number of days). Tintin is very busy with making all the preparations and needs your help. He wants you to tell him the number of ways of selecting the V different visits following the conditions so that he can plan more accurately and pace up the search.
Can you help him in planning and searching Professor Calculus?
Note: Since the number of ways can be large, print the answer modulo 10^9+7
gif source: google
Input Format
The only line of input consists of three space-separated integers, V (number of different visits), M (minimum number of days) and X (maximum number of days).
Constraints
1<= M <=X <=10^18
1<= V <=200
Output Format
Print the number of ways modulo 10^9+7.
Note: There is a new line at the end of the output.
Sample TestCase 1
Input
2 1 3
Output
14
Explanation
The two things they can do on a visit:
Search for Professor
Take Rest
Minimum number of days, M = 2
Maximum number of days, X = 3
Number of different visits to be selected, V = 2
Let’s Denote searching for Professor with S and taking rest with R.
Different visits of 1 day are:
S - Searching for Professor
R - Taking Rest
Different visits of 2 days are:
RS - Resting on day 1 and searching on day 2
SR - Searching on day 1 and taking rest on day 2
SS - Searching on both the days, 1 and 2
Note: RR can not be a visit as they can not take rest for two days consecutively.
Different visits of 3 days are:
RSR - Resting on day 1 and day 3. Searching on day 2.
RSS - Resting on day 1. Searching on day 2 and day 3.
SRS - Searching on day 1 and day 3. Taking rest on day 2
SSR - Searching on day 1 and day 2. Taking rest on day 3
SSS - Searching on all the three days, 1, 2 and 3
The number of ways of selecting the V (2) different visits of same duration are 14
[S, R], [RS, SR], [RS, SS], [SR, SS], [RSR, RSS], [RSR, SRS], [RSR, SSR], [RSR, SSS], [RSS, SRS], [RSS, SSR], [RSS, SSS], [SRS, SSR], [SRS, SSS], [SSR, SSS]
Answers
Answer:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1000000007;
map<ll, ll> F;
ll powmod(ll a, ll b) {
ll res=1;
a%=mod;
assert(b>=0);
for(;b;b>>=1) {
if(b&1)
res=res*a%mod;
a=a*a%mod;
}
return res;
}
ll fib(ll n) {
if (F.count(n)) return F[n];
ll k = n/2;
if (n % 2==0) {
return F[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1)) % mod;
} else {
return F[n] = (fib(k) * fib(k+1) + fib(k-1) * fib(k)) % mod;
}
}
ll nCr(ll n, ll r, ll inv) {
if (r > n)
return 0;
ll res = 1;
while (r) {
res = (res * n) % mod;
n -= 1;
r -= 1;
}
res = (res * inv) % mod;
return res;
}
int main() {
F[0] = 1; F[1] = 2;
ll v, l, r;
cin >> v >> l >> r;
ll curr_fib = fib(l), prev_fib = fib(l-1);
ll ans = 0, inv = 1;
for (ll i = 1; i <= v; i++)
inv = (inv * i) % mod;
inv = powmod(inv, mod-2);
for (ll x = l; x <= r; x++) {
ans = (ans + nCr(curr_fib, v, inv)) % mod;
ll new_fib = (curr_fib + prev_fib) % mod;
prev_fib = curr_fib;
curr_fib = new_fib;
}
cout << ans << endl;
}
Explanation:
Answer:
[2:16 PM, 12/11/2020] Vishwas: Professor Calculus was working with the government on an important project. The aim of the project was to make a shark submarine which would help the government to work in the areas which were highly dominated by the sharks. The enemies got to know about it and they had kidnapped Professor Calculus.
image source: google
The government is searching for him and has also informed Tintin and detectives (Thomson and Thompson). Tintin and Snowy are preparing to search for Professor Calculus. Tintin has also informed everything to Captain Haddock and his first response is - “Blistering Barnacles”. They all are set to pay a visit to different cities to search for Professor. They can only do two things while paying visits to different cities:
Search for Professor
Take Rest
image source: google
A visit can be of a single or multiple days. During a visit, they cannot take rest for two days consecutively. Tintin has selected a range of minimum (M) and maximum (X) number of days required to search for the Professor. Tintin wants to select V different visits between the minimum and the maximum number of days (both inclusive). The only condition is that the visits should be of the same duration (number of days). Tintin is very busy with making all the preparations and needs your help. He wants you to tell him the number of ways of selecting the V different visits following the conditions so that he can plan more accurately and pace up the search.
Can you help him in planning and searching Professor Calculus?
Note: Since the number of ways can be large, print the answer modulo 10^9+7
gif source: google
Input Format
The only line of input consists of three space-separated integers, V (number of different visits), M (minimum number of days) and X (maximum number of days).
Constraints
1<= M <=X <=10^18
1<= V <=200
Output Format
Print the number of ways modulo 10^9+7.
Note: There is a new line at the end of the output.
Sample TestCase 1
Input
2 1 3
Output
14
Explanation
The two things they can do on a visit:
Search for Professor
Take Rest
Minimum number of days, M = 2
Maximum number of days, X = 3
Number of different visits to be selected, V = 2
Let’s Denote searching for Professor with S and taking rest with R.
Different visits of 1 day are:
S - Searching for Professor
R - Taking Rest
Different visits of 2 days are:
RS - Resting on day 1 and searching on day 2
SR - Searching on day 1 and taking rest on day 2
SS - Searching on both the days, 1 and 2
Note: RR can not be a visit as they can not take rest for two days consecutively.
Different visits of 3 days are:
RSR - Resting on day 1 and day 3. Searching on day 2.
RSS - Resting on day 1. Searching on day 2 and day 3.
SRS - Searching on day 1 and day 3. Taking rest on day 2
SSR - Searching on day 1 and day 2. Taking rest on day 3
SSS - Searching on all the three days, 1, 2 and 3
The number of ways of selecting the V (2) different visits of same duration are 14
def binomialCoef(n, k):
C = [[0 for x in range(k+1)] for x in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
if j == 0 or j == i:
C[i][j] = 1
else:
C[i][j] = C[i-1][j-1] + C[i-1][j]
return C[n][k]
N,X,V = map(int,input().split())
myfib = [1,1]
for i in range(V):
myfib.append(myfib[-1]+myfib[-2])
myfib = myfib[2:]
print(sum([binomialCoef(myfib[i],N) for i in range(X-1,V)]))
Explanation:
list insde