PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Bharat Singla
Tester: Aryan Choudhary
Editorialist: Lavish Gupta
DIFFICULTY:
Medium
PREREQUISITES:
Expected Values, Combinatorics
PROBLEM:
Chef, who is a chef by profession as well, has created N pies (enumerated 1 through N) and has placed them in a row. Now he wants to taste all the pies, but by following a rather peculiar order of tasting.
At each step, he chooses (uniformly randomly and independently) either the current leftmost pie or the rightmost pie, and eats that pie.
For example, if N = 7, then one valid order of tasting the pies is (1, 2, 7, 3, 4, 6, 5). However, (1, 2, 7, 6, 4, 5, 3) is not a valid order.
Chef can’t wait to taste all the pies, so for each i (1 \leq i \leq N), he wants to know the expected value of the number of steps he’ll need to eat the i^{th} pie.
It can be shown that each expected value can be expressed as a fraction \frac{P}{Q}. You should compute P \cdot Q^{-1} modulo 10^9+7, where Q^{-1} denotes the modular multiplicative inverse of Q under 10^9+7
EXPLANATION:
Let’s denote the operation of choosing leftmost pie by L, and choosing rightmost pie by R.
Let us consider the P^{th} pie from the left, and try to calculate the Expected value for this pie.
There are two ways to pick this pie - either using an L operation, or using an R operation.
Let us focus on the case when the P^{th} pie was chosen using an L operation.
A Natural, but incorrect(?) approach
Assume that this pie was chosen after P+K operations. This means that number of L operations will be P, and the number of R operations will be K. Also, the last operation should be L.
Number of ways to choose pie after P+K operations such that the last operation is L is same as Number of ways to arrange \#(P-1) Ls and \#K Rs. Also, Because choosing L and R are equiprobable, the probability of each such arrangement is (\frac{1}{2})^{P+K}.
Therefore, the Probability of choosing P^{th} pie after P+K operations such that the last operation was L = \binom{P-1 + K}{K} \cdot (\frac{1}{2})^{P+K}.
And the Expected value can be calculated as:
E_P = \sum_{K = 0}^{N-P} \binom{P-1 + K}{K} \cdot (\frac{1}{2})^{P+K} \cdot (P+K)
Notice the constraints on K. The maximum number of R operations can be N-P, as we want the P^th pie to be chosen by an L operation.
The issue with the above summation is, it is difficult to calculate its value efficiently.
Do let us know in the comments if you have been able to calculate it efficiently!
A Magical, working approach
In this approach, we will continue choosing the pies even after we have chosen the P^{th} pie. This complete simulation can be represented as a string of length N having L and R as characters.
Let say that in the complete process, the R operations were done a total of K times.
Also, let say that the R operations were done a total of i times before choosing the P^{th} pie using L operation.
Because the P^{th} pie is chosen using L operation, the maximum value of K can be N-P.
Total number of strings such that the P^{th} pie is chosen using L operation will be
S_P = \sum_{k = 0}^{N-P} \sum_{i = 0}^k \binom{P-1+i }{i} \cdot \binom{N-(P+i)}{k-i} \cdot (P+i)
On Simplifying
Clubbing first and third term, we get
S_P = \sum_{k = 0}^{N-P} \sum_{i = 0}^k P \cdot \binom{P+i }{i} \cdot \binom{N-(P+i)}{k-i}
Let T = \sum_{i = 0}^k \binom{P+i }{i} \cdot \binom{N-(P+i)}{k-i}
On further Simplifying
We know that
(1-x)^{-N} = \sum_{r = 0}^{\infty} \binom{N-1+r}{r}x^r
Consider the following two binomial expansions:
(1-x)^{-(P+1)} = \sum_{r_1 = 0}^{\infty} \binom{P+r_1}{r_1}x^{r_1}
(1-x)^{-(N - P - K + 1)} = \sum_{r_2 = 0}^{\infty} \binom{N - P - K+r_2}{r_2}x^{r_2}
The coefficient of x^K in (1-x)^{-(P+1)} \cdot (1-x)^{-(N - P - K + 1)} can be written as
\sum_{i = 0}^k \binom{P+i }{i} \cdot \binom{N-(P+i)}{k-i}
which is same as T. Hence,
T = x^K: (1-x)^{-(P+1)} \cdot (1-x)^{-(N - P - K + 1)}
T = x^K: (1-x)^{-(N-K)}
T = \binom{N+1}{k}
Substituting back in S_P, we have
S_P = P \cdot \sum_{k = 0}^{N-P} \binom{N+1}{k}
Note that the sum S_P has currently accounted only for the case when the P^{th} element is chosen using an L operation.
To account for the case when P^{th} element is chosen using an R operation, we can observe that P^{th} element from the left is (N-P+1)^{th} element from the right, and therefore the contribution coming from this case will be same as the contribution from (N-P+1)^{th} element from the left (because L and R operations are symmetric).
Therefore, the final value of S_P will be:
S_P = \bigg( P \cdot \sum_{k = 0}^{N-P} \binom{N+1}{k} \bigg) + \bigg((N-P+1) \cdot \sum_{k = 0}^{P-1} \binom{N+1}{k} \bigg)
Each term can be calculated efficiently using the running sum.
Finally, each string is equiprobable with probability (\frac{1}{2})^N. Therefore, the expected value for the P^{th} pie can be represented as:
E_P = (\frac{1}{2})^N \cdot S_P
TIME COMPLEXITY:
The above algorithm can be implemented in O(N \cdot \log_{}N) as well as O(N) depending on the pre-computation and implementation details.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int MAX = 100010, mod = 1e9 + 7;
ll inv[MAX];
ll dp[MAX];
ll rpe(ll a, int b) {
ll ans = 1;
while (b != 0) {
if (b & 1)ans = ans * a % mod;
a = a * a % mod; b >>= 1;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
inv[i] = mod - (mod / i) * inv[mod % i] % mod;
}
int t; cin >> t;
while (t--) {
int n; cin >> n;
dp[2] = (ll)(n + 1) * n % mod * inv[2] % mod;
for (int i = 3; i <= n + 1; i++) {
dp[i] = dp[i - 1] * (n - i + 2) % mod * inv[i] % mod;
}
for (int i = n; i >= 2; i--) {
dp[i] = (dp[i] + dp[i + 1]) % mod;
}
for (int i = 2; i <= n + 1; i++) {
dp[i] = dp[i] * (i - 1) % mod;
}
ll den = rpe(2LL, mod - n - 1);
for (int i = 2; i <= n + 1; i++) {
cout << ((dp[i] + dp[n - i + 3]) % mod * den % mod) << " ";
}
cout << endl;
}
return 0;
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
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;
}
assert(l<=x&&x<=r);
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,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using namespace atcoder;
//using mint = modint998244353;
using mint = modint1000000007;
using vm = vector<mint>;
std::ostream& operator << (std::ostream& out, const mint& rhs) {
return out<<rhs.val();
}
// Ref - https://www.codechef.com/viewsolution/41909444 Line 827 - 850.
const int maxnCr=2e6+5;
array<mint,maxnCr+1> fac,inv;
mint nCr(lli n,lli r)
{
if(n<0||r<0||r>n)
return 0;
return fac[n]*inv[r]*inv[n-r];
}
void pre(lli n)
{
fac[0]=1;
for(int i=1;i<=n;++i)
fac[i]=i*fac[i-1];
inv[n]=fac[n].pow(mint(-2).val());
for(int i=n;i>0;--i)
inv[i-1]=i*inv[i];
assert(inv[0]==mint(1));
}
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
vm solveN2(const lli n){
vm a(n+1),p2inv(n+1,1),b;
p2inv[1]/=2;
for(int i=2;i<=n;++i)
p2inv[i]=p2inv[i-1]*p2inv[1];
for(int i=1;i<=n;++i){
mint &cur=a[i];
for(int j=i;j<=n;++j){
cur+=j*nCr(j-1,i-1)*p2inv[j];
}
}
for(int i=1;i<=n;++i)
b.pb(a[i]+a[n-i+1]);
return b;
};
vm solveN(const lli n){
vm a(n+1),b;
mint sum=0;
for(lli p=n;p>0;p--){
sum+=nCr(n+1,p+1);
a[p]=p*sum;
}
const mint p2n = mint(2).pow(n).inv();
for(int i=1;i<=n;++i)
b.pb((a[i]+a[n-i+1])*p2n);
return b;
};
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
pre(maxnCr);
// T=readIntLn(1,10);
cin>>T;
while(T--)
{
cin>>n;
// n=readIntLn(1,1e5);
const auto a=solveN(n);
for(auto x:a)
cout<<x<<" ";
cout<<endl;
} aryanc403();
readEOF();
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
const ll z = 1000000007 ;
const int N = 100005 ;
ll fact[N];
ll inverses[N] ;
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 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);}
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
fact[0] = 1 ;
for(ll i = 1 ; i < N ; i++)
{
fact[i] = (fact[i-1]*i)%z ;
inverses[i] = inverse(i , z) ;
}
int t ;
cin >> t ;
while(t--)
{
int n;
cin >> n ;
vector<ll> val(n+1) ;
int r = 0 ;
for(int i = n ; i >= 0 ; i--)
{
if(r == 0)
val[i] = 1 ;
else
val[i] = (((val[i+1] * (n-r+2))%z)*(inverses[r]))%z ;
r++ ;
}
for(int i = n-1 ; i >= 0 ; i--)
val[i] = (val[i+1] + val[i])%z ;
ll den = inverse(power(2 , n , z) , z) ;
for(int i = 1 ; i <= n ; i++)
{
val[i] *= i ;
val[i] %= z ;
val[i] *= den ;
val[i] %= z ;
}
vector<ll> ans(n+1) ;
for(int i = 1 ; i <= n ; i++)
{
ans[i] = (val[i] + val[n+1-i])%z ;
cout << ans[i] << ' ';
}
cout << endl ;
}
return 0;
}