PROBLEM LINK:
Editorialist & Author: Aditi Sahu
Tester : Krish Rustagi
DIFFICULTY:
EASY
PREREQUISITES:
DP, MATHS
PROBLEM:
There are T test cases. In each case, you are given N and K (where N is total length and K is the ominous number) .You have to find total arrangements of tanks except K number of Tanks.
EXPLANATION:
Let’s have a look on the pattern it follows:
If we consider one more arrangement with no tanks then:
for N=2 total possible arrangements are 3(- - , - *, *-)
for N=3 total possible arrangements are 5(- - - , *- -, - * -, - - *, * - *)
for N=4 total possible arrangements are 8( - - - - , * - - - , - * - - , - - * -, - - - *, * - * -, * - - * , - * - *)
for N=5 total possible arrangements are 13
From above we observed that it is a fibonacci series.
So to get total arrangements we will find its fibonacci number and subtract 1 for no tanks.
Fibonacci: A need of precomputation is requried ,first calculate and store in some array so that we can later use it for our purpose.
f =[]*1000000
f[1]=2
f[2]=3
fib():
For i in range(3,1000000):
F[i] = f[i-1]+f[i-2]
To Calculate nCr: An efficient approach will be to reduce the better approach to an efficient one by precomputing the inverse of factorials. Precompute inverse of factorial in O(n) time and then queries can be answered in O(1) time. Inverse of 1 to N natural numbers can be computed in O(n) time using the Modular multiplicative inverse. Using recursive definition of factorial, the following can be written:
n! = n * (n-1) !
taking inverse on both side
inverse( n! ) = inverse( n ) * inverse( (n-1)! )
To find how many arrangements are possible with K tanks:
To find arrangements with k tanks let’s take example where N=4 and K=2
Let’s position the first tank at 1st position now possible position for 2nd tank is at 3rd or at 4th
*-*-
*--*
So total possible position where tanks can occupy there space is =3
And we want only two tanks in total n(n=4) length.
Total arrangement will be=3C2
arrangements with K tanks: (n-k+1)Ck
Answer: Total-(k tanks arrangements)
SOLUTIONS:
Setter's Solution(C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
const ll M = 1e9 + 7;
vector<ll> f(100003);
const int N = 100003;
ll t;
unsigned long long power(unsigned long long x,
int y, int p)
{
unsigned long long res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
unsigned long long modInverse(unsigned long long n,
int p)
{
return power(n, p - 2, p);
}
unsigned long long nCrModPFermat(unsigned long long n,
int r, int p)
{
if (n < r)
return 0;
if (r == 0)
return 1;
unsigned long long fac[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % p;
return (fac[n] * modInverse(fac[r], p) % p
* modInverse(fac[n - r], p) % p)
% p;
}
void fib()
{
f[0] = 0;
f[1] = 1;
for(ll i = 2; i <= N; i++)
{
f[i] = ((f[i - 1] % M) + (f[i - 2] % M)) % M;
}
}
ll factorialNumInverse[N + 1];
ll naturalNumInverse[N + 1];
ll fact[N + 1];
void InverseofNumber(ll p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(ll p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void factorial(ll p)
{
fact[0] = 1;
for (int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * i) % p;
}
}
ll Binomial(ll N, ll R, ll p)
{
ll ans = ((fact[N] * factorialNumInverse[R])
% p * factorialNumInverse[N - R])
% p;
return ans;
}
int mod(ll num, ll modValue)
{
return ( modValue- ( (0-num) % modValue) );
}
void solve()
{
ll n, k;
cin >> n >> k;
ll ans;
ans = (f[n+2] - 1) % M;
ll x = n - k + 1;
ll sub = Binomial(x, k, M);
ans = (ans - sub);
if(ans < 0)
{
ans = mod(ans, M);
}
cout<< ans << "\n";
}
int main()
{
fast
fib();
InverseofNumber(M);
InverseofFactorial(M);
factorial(M);
cin >> t;
while(t--)
{
solve();
}
}
Tester’s Solution(Python)
N = 1000000
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)
def InverseofNumber(p):
naturalNumInverse[0] = naturalNumInverse[1] = 1
for i in range(2, N + 1, 1):
naturalNumInverse[i] = (naturalNumInverse[p % i] *
(p - int(p / i)) % p)
def InverseofFactorial(p):
factorialNumInverse[0] = factorialNumInverse[1] = 1
for i in range(2, N + 1, 1):
factorialNumInverse[i] = (naturalNumInverse[i] *
factorialNumInverse[i - 1]) % p
def factorial(p):
fact[0] = 1
for i in range(1, N + 1):
fact[i] = (fact[i - 1] * i) % p
def Binomial(N, R, p):
ans = ((fact[N] * factorialNumInverse[R])% p *
factorialNumInverse[N - R])% p
return ans
p = 1000000007
fib = [0, 1]
for i in range(2, 1000000):
fib.append((fib[i - 1] % p + fib[i - 2] % p) % p)
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for _ in range(int(input())):
n, k = map(int, input().split())
ans = fib[n + 2] - 1
sub = Binomial(n - k + 1, k, p)
ans -= sub
if(ans < 0):
ans = (p - (-ans) % p) % p
print(ans)