TASTYPIE - Editorial

[lavish315]

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;
}

[anshugarg12]

Hey, I was able to solve using that incorrect approach (took me 2hrs though ).

The summation is:

\sum_{K=0}^{N-P}\binom{P-1+K}{K} . (\frac{1}{2})^{P+K}.(P+K)

= \frac{P}{2^{P}}\sum_{K=0}^{N-P}\binom{P+K}{P} . (\frac{1}{2})^{K} (multiply divide by P and take P + K, P in ncr term)

= \frac{P}{2^{P}} . [x^P]((x + \frac{1}{2})^P + (x + \frac{1}{2})^{P+1} + ... + (x + \frac{1}{2})^{N})

Adding the remaining terms as they won’t contribute to [x^P]

= \frac{P}{2^{P}} . [x^P](\sum_{i=0}^{N}(x + \frac{1}{2})^i)

Applying geometric progression formula

= \frac{P}{2^{P}} . [x^P]\frac{(1 - (x+\frac{1}{2})^{N+1})}{\frac{1}{2}-x}

= \frac{2.P}{2^{P}} . [x^P]\frac{(1 - (x+\frac{1}{2})^{N+1})}{1-2x}

Expanding the denominator as GP

= \frac{P}{2^{P-1}} . [x^P](1 - (x+\frac{1}{2})^{N+1}).(1 + 2x + 4x^2 + 8x^3 + ...)

= \frac{P}{2^{P-1}} .[ [x^P](1 + 2x + 4x^2 + 8x^3 + ...) - [x^{P}] (x+\frac{1}{2})^{N+1}.(1 + 2x + 4x^2 + 8x^3 + ...)]

The first term is easy to calculate, moving to second term

[x^{P}] (x+\frac{1}{2})^{N+1}.(1 + 2x + 4x^2 + 8x^3 + ...) = \sum_{i=0}^{P}\binom{N+1}{i}.\frac{1}{2^{N + 1 - i}}.2^{P-i} = \sum_{i=0}^{P}\binom{N+1}{i}.\frac{2^P}{2^{N + 1}} (removing 2^i from numerator and denominator)

There can be off by one errors but the approach is correct.

Thanks.

[denisov]

I had similar idea, but I think it is easier to do it without GP. Just calculate 1-(x+1/2)^{N+1} using binomial formula and then just divide by 1-2x.

[shubu9211]

Some godly stuff!! Maths heavy

[tabr]

Really nice problem!

There is another way to simplify T. Let Q be N-P-k, so T = \sum_{i=0}^k\binom{P+i}{P}\cdot\binom{Q+(k-i)}{Q}.

Imagine that you have P+Q+1 white balls and k bars. There are \binom{P+Q+k+1}{k} ways to arrange them. Let’s color (P+1)-th ball black. There are P balls and i bars its leftside and Q balls and k - i bars rightside. i can be from 0 to k so we can get T = \binom{P+Q+k+1}{k}.

[islingr]

There’s a pretty clean way to do by setting up a recurrence and then using generating functions, sort of explains where the GP comes from in @anshugarg12’s solution, and also gives a clean implementation.

Number it from 0 to N - 1 instead. If f_n(i) is the expected steps to eat the i-th pie. You get the recurrence f_n(i) = 1 + \frac{1}{2} (f_{n - 1}(i) + f_{n - 1}(i - 1)) by making cases on if the leftmost element was picked or the last.

Now define F_n(x) = \sum_{0 \le i < n} f_n(i) x^i, the above recurrence gives you a recurrence for F_n, F_n(x) = \frac{1 - x^n}{1 - x} + (\frac{1 + x}{2}) F_{n - 1}(x) with the base case F_0(x) = 0.

Define G_n(x) = (1 - x) F_n(x) and a(x) = \frac{1 + x}{2} for convenience.
G_n(x) = (1 - x^n) + a(x) G_{n - 1}(x) = \sum_{0 \le i < n} a(x)^i(1 - x^{n - i})
by inducting.

Splitting the two terms, you end up with G_n(x) = \frac{1 - a(x)^n}{1 - a(x)} - x \cdot \frac{a(x)^n - x^n}{a(x) - x}.
Note that 1 - a(x) = a(x) - x = \frac{1 - x}{2}, on plugging this in and simplifying you end up with G_n(x) = 2 \cdot \frac{(1 + x^{n + 1}) - (1 + x)a(x)^n}{1 - x} = \frac{2(1 + x^{n + 1}) - \frac{1}{2^{n - 1}} (1 + x)^{n + 1}}{1 - x}.

Bringing F_n(x) back, F_n(x) = \frac{G_n(x)}{1 - x} = \frac{2(1 + x^{n + 1}) - \frac{1}{2^{n - 1}} (1 + x)^{n + 1}}{(1 - x)^2}.
Now you could expand it out and try to find the exact coefficients but that’s unnecessary.
Note that if A(x) = \sum_{i \ge 0} a_i x^i then \frac{A(x)}{1 - x} = \sum_{i \ge 0} \left(\sum_{0 \le j \le i} a_j\right) x^i, ie, multiplying by \frac{1}{1 - x} is equivalent to computing the prefix sum.
The numerator can be found in O(N) using binomial theorem, then compute prefix sums of the numerator twice, corresponding to the two multiplications by \frac{1}{1 - x} and you get the answer.

Here’s the code.

[hackapie]

Sorry for bothering but can you explain
What is [x^P] ?
How did you convert summation to [x^P]…?
Again how did you convert [x^P] to summation while calculating the second term?

[aryanc403]

@anshugarg12

Expanding the denominator as GP

Nice one. When I was solving it I went until this polynomial formula then mostly gave up on simplifying it.

Also after you ACed it I was waiting for you to solve the rest of the problems so that you can break @tabr 's 5 consecutive starters win streak. In the end, he won his 6th consecutive starter.

[anshugarg12]

Ohhh, a special congrats to tabr. Btw I tried STRFLIPS but couldn’t solve it in the remaining time, also I was not in mood for the contest. I tried last problem for almost an hour but couldn’t solve, went away and then came back after 30 minutes it hurted by ego and finally solved it. Though its difficult but still I will try to break his streak .