PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Lavish Gupta
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh
DIFFICULTY:
To be calculated
PREREQUISITES:
Computing binomial coefficients modulo a prime
PROBLEM:
There is a stone of mass 2^N, initially lying at the origin. For the next N seconds, each stone of mass M at position X splits into one stone of mass \frac{M}{2} going to position X-1 and another of mass \frac{M}{2} going to position X+1.
Given L and R, find for each position i such that L \leq i \leq R how many stones lie at position i at the end of the process.
EXPLANATION:
Hint
Think of the stone of mass 2^N as being 2^N separate stones of mass 1. Encode the movement of each stone as a binary string of length N, distinct stones receiving distinct strings. Now relate this encoding to the final position.
Full solution
Instead of stones halving in mass, it becomes a bit easier to think of the problem as involving 2^N stones, each of mass 1. The given operation then essentially says that at each position, half the stones present there move left and the other half move right.
Now note that the movement of any given stone can be represented by a binary string of length N — the i-th character of the string is 1
if this stone moved right on the i-th move, and 0
if it moved left.
Under this setup, it’s easy to see that no two stones will receive the same binary string, i.e, no two stones have the exact same movement pattern.
Proof
This can be proved by induction on N. If N = 1 the result is trivial, since there are 2 stones, one moving left and the other moving right on the only move made.
For N > 1, after the first move there are 2^{N-1} stones on -1 and 2^{N-1} on +1. Clearly, any pair consisting of a stone at -1 and a stone at +1 has different binary strings, since the very first character differs.
Now, consider only those stones at -1. They correspond to the process with N-1 and hence any two within this pile will also differ eventually, by the inductive hypothesis. Similarly, any two stones at +1 will also differ eventually.
With 2^N stones and 2^N binary strings, it’s easy to see that there is a bijective mapping between stones and binary strings.
Now, we use this information to actually solve the problem at hand.
Consider a stone such that its binary string has x ones and y zeros.
It made x steps right and y steps left, which means it ended up at position x - y.
Let’s turn that around. Suppose we fix a position k. How many stones ended up at position k?
Well, we know that if a stone made x steps right and y steps left and then ended up at k, we must have x - y = k.
On the other hand, clearly we also have x + y = N, the total number of moves made.
Note that these equations give us a unique solution for the pair (x, y) — namely, x = \frac{k + N}{2} and y = \frac{N - k}{2}. Of course, x and y do need to be integers, so if k and N have different parities then no stone can end up at position k.
Now, say we fix position k and calculate x and y. How many stones have binary strings corresponding to this x and y?
As established earlier, each binary string corresponds to a single stone and vice versa, which means that all we need to do is to compute the number of binary strings of length N consisting of x ones and y zeros!
A simple combinatorial argument shows that this number is just \binom{x+y}{x} = \binom{N}{x} — choose which x of the N positions are ones, and the others are automatically fixed to contain zeros.
Note that the binomial coefficient needs to be calculated modulo 10^9 + 7, so if you don’t know how to do that a tutorial has been linked above.
TIME COMPLEXITY:
\mathcal{O}(N\log MOD) or \mathcal{O}(N) per test.
CODE:
Setter (C++)
#define ll long long
#define dd long double
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#define tll tuple<ll ,ll , ll>
#define pll pair<ll ,ll>
#include<bits/stdc++.h>
/*#include<iomanip>
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<bitset>*/
dd pi = acos(-1) ;
ll z = 1000000007 ;
ll inf = 10000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 = 202976689 ;
ll mod2 = 203034253 ;
ll fact[1000005] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ; return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 , g; g = e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return g ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r|| (n < 0) || (r < 0)) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
ll seed;
mt19937 rnd(seed=chrono::steady_clock::now().time_since_epoch().count()); // include bits
void initialize()
{
fact[0] = 1 ;
for(ll i = 1 ; i < 1000005 ; i++)
fact[i] = (fact[i-1]*i)%z ;
return ;
}
ll get_ans(ll n, ll x)
{
ll one = n+x ;
if(one%2 == 1)
return 0 ;
one /= 2 ;
ll min_one = n - one ;
return ncr(n , one) ;
}
void solve()
{
ll n, l, r ;
cin >> n >> l >> r ;
for(ll i = l ; i <= r ; i++)
{
ll ans = get_ans(n , i) ;
if(i == l)
cout << ans ;
else
cout << ' ' << ans ;
}
cout << endl ;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
initialize() ;
int t ;
cin >> t ;
while(t--)
solve() ;
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Tester (C++)
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0, sum = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
ll po(ll x, ll n ){
ll ans=1;
while(n>0){
if(n&1) ans=(ans*x)%mod;
x=(x*x)%mod;
n/=2;
}
return ans;
}
const ll MX=2000000;
ll fac[MX], ifac[MX];
void pre(){
fac[0]=1;
rep_a(i,1,MX) fac[i]= (i*fac[i-1])%mod;
rep(i,MX) ifac[i]= po(fac[i], mod-2);
}
ll ncr(ll n, ll r){
if(r>n || r<0 || n<0) return 0;
return (fac[n]*((ifac[r]*ifac[n-r])%mod))%mod;
}
void solve()
{
int n = readIntSp(1,1e6);
int l = readIntSp(-n,n);
int r = readIntLn(-n,n);
assert(l<=r);
sum_n+=(r-l+1);
l+=n;
r+=n;
if(l&1){
cout<<0<<" ";
l++;
}
int f = 0;
if(r&1) f=1;
l/=2;
r/=2;
rep_a(i,l,r) cout<<ncr(n,i)<<" 0 ";
cout<<ncr(n,r)<<" ";
if(f) cout<<'0';
cout<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,100);
pre();
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_m<=1e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_m <<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist (Python)
MAXN = 10**6 + 10
mod = 10**9 + 7
fac = [i for i in range(MAXN)]
fac[0] = 1
for i in range(1, MAXN):
fac[i] *= fac[i-1]
fac[i] %= mod
ifac = [0 for i in range(MAXN)]
ifac[-1] = pow(fac[-1], mod-2, mod)
for i in range(MAXN-2, -1, -1):
ifac[i] = (i+1)*ifac[i+1]
ifac[i] %= mod
def C(n, r):
if n < 0 or r < 0 or r > n:
return 0
return (fac[n] * ifac[r] * ifac[n-r])%mod
for _ in range(int(input())):
n, L, R = map(int, input().split())
for i in range(L, R+1):
if (n + i)%2 == 0:
x = (n + i)//2
print(C(n, x), end = ' ')
else:
print('0 ', end = '')
print('')