PROBLEM LINK:
Author & Editoralist: Jafar Badour
Tester: Teja Reddy
PROBLEM EXPLANATION
You are given a sequence A_1, A_2, \ldots, A_N. We want to generate a sequence F_1, F_2, \ldots, F_N using the following process:
- initially, F_i = 0 for each valid i.
- A has 2^N-1 non-empty subsequences. For each of these subsequences (let’s denote it by S_1, S_2, \ldots, S_L, where L is the length of this subsequence), perform the following assignment: for each i (1 \le i \le L), add S_i to F_i.
Find the final sequence F. Since its elements could be large, calculate them modulo 10^9+7.
PREREQUISITES:
fft
QUICK EXPLANATION:
Try to solve the task in O(n^2). You will have expressions containing {N}\choose{k}
We can break {N}\choose{k} into \frac{N!}{(k!)(N-k)!}
You can notice that you can calculate your answers with a simple convolution.
EXPLANATION:
F_i denotes the sum of all elements which have order i (has i-1 elements to the left of it) in all subsequences with length more than or equal to i.
Let’s look how an O(n^2) solution looks like:
for(int K = 1 ; K <= n ; K++)
for(int i = K ; i <= n ; i++)
F[K] += A[i] * POW(2,n-i) * nChooseK(i-1,K-1)
What we are doing here exactly is, we are calculating the contribution of each element to every number in our answer vector.
How much does an element with index i add to F_K ?
For each subsequence such that its K_{th} value is equal to A_i we should add A_i to F_K
The number of these subsequences is 2^{n-i}*{{i-1}\choose{K-1}}
Because it must have K-1 elements to its left, and we can pick anything from the right (any subset).
We can break {N}\choose{k} into \frac{N!}{(k!)(N-k)!}
Let’s re-write our code:
for(int K = 1 ; K <= n ; K++)
for(int i = 1 ; i <= n ; i++)
F[K] += A[i] * POW(2,n-i) * factorial[i-1] * modInverse(factorial[K-1]) * modinverse(factorial[i-K])
Writing the instruction inside the loops mathematically;
F_K=F_K + A_i*2^{n-i}*(i-1)!*\frac{1}{(K-1)!}*\frac{1}{(i-K)!} (*)
Notice that the only term that depends on both values of both (i,K) is \frac{1}{(i-K)!}.
Select some K and write the above expression for every element. You will notice that (i-K) will decrease one by one to the left. Thus we can calculate the sum of multiplications with a convolution.
Let’s make 2 polynomials:
A=a_1*x^1+a_2*x^2+a_3*x^3+\ldots+a_n*x^n
where:
a_i=A_i * 2^{n-i} * (i-1)!
B=b_0*x^0+b_1*x^1+b_2*x^2+\ldots+b_n*x^n
where:
b_i= \frac{1}{(n-i)!}
If C is our resulting vector:
C=c_0*x^0+c_1*x^1+c_2*x^2+\ldots+c_n*x^m
F_K = c_{n+K}*\frac{1}{(K - 1)!}
Notice that \frac{1}{(K - 1)!} is a common factor from (*)
You should use NTT or an improved implementation of fft that handles modulo.
My code uses implementation from ITMO notebook which is black-box friendly if you want to try the problem and you don’t understand fft well.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef double dbl;
typedef long long ll;
#define pw(x) (1LL << (x))
#define forn(i, n) for (int i = 0; i < (n); i++)
namespace fft
{
const int maxBase = 18;
const int maxN = 1 << maxBase;
struct num
{
dbl x, y;
num(){}
num(dbl xx, dbl yy): x(xx), y(yy) {}
num(dbl alp): x(cos(alp)), y(sin(alp)) {}
};
inline num operator + (num a, num b) { return num(a.x + b.x, a.y + b.y); }
inline num operator - (num a, num b) { return num(a.x - b.x, a.y - b.y); }
inline num operator * (num a, num b) { return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline num conj(num a) { return num(a.x, -a.y); }
const dbl PI = acos(-1);
num root[maxN];
int rev[maxN];
bool rootsPrepared = false;
void prepRoots()
{
if (rootsPrepared) return;
rootsPrepared = true;
root[1] = num(1, 0);
for (int k = 1; k < maxBase; ++k)
{
num x(2 * PI / pw(k + 1));
for (int i = pw(k - 1); i < pw(k); ++i)
{
root[2 * i] = root[i];
root[2 * i + 1] = root[i] * x;
}
}
}
int base, N;
int lastRevN = -1;
void prepRev()
{
if (lastRevN == N) return;
lastRevN = N;
forn(i, N) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (base - 1));
}
void fft(num *a, num *f)
{
forn(i, N) f[i] = a[rev[i]];
for (int k = 1; k < N; k <<= 1) for (int i = 0; i < N; i += 2 * k) forn(j, k)
{
num z = f[i + j + k] * root[j + k];
f[i + j + k] = f[i + j] - z;
f[i + j] = f[i + j] + z;
}
}
num a[maxN], b[maxN], f[maxN], g[maxN];
ll A[maxN], B[maxN], C[maxN];
void _multMod(int mod, bool eq)
{
forn(i, N)
{
int x = A[i] % mod;
a[i] = num(x & (pw(15) - 1), x >> 15);
}
forn(i, N)
{
int x = B[i] % mod;
b[i] = num(x & (pw(15) - 1), x >> 15);
}
fft(a, f);
if (!eq) {
fft(b, g);
} else {
for (int i = 0; i < N; i++) g[i] = f[i];
}
forn(i, N)
{
int j = (N - i) & (N - 1);
num a1 = (f[i] + conj(f[j])) * num(0.5, 0);
num a2 = (f[i] - conj(f[j])) * num(0, -0.5);
num b1 = (g[i] + conj(g[j])) * num(0.5 / N, 0);
num b2 = (g[i] - conj(g[j])) * num(0, -0.5 / N);
a[j] = a1 * b1 + a2 * b2 * num(0, 1);
b[j] = a1 * b2 + a2 * b1;
}
fft(a, f);
fft(b, g);
forn(i, N)
{
ll aa = f[i].x + 0.5;
ll bb = g[i].x + 0.5;
ll cc = f[i].y + 0.5;
C[i] = (aa + bb % mod * pw(15) + cc % mod * pw(30)) % mod;
}
}
void prepAB(int n1, int n2)
{
base = 1;
N = 2;
while (N < n1 + n2) base++, N <<= 1;
for (int i = n1; i < N; ++i) A[i] = 0;
for (int i = n2; i < N; ++i) B[i] = 0;
prepRoots();
prepRev();
}
void mult(int n1, int n2, int mod, bool eq)
{
prepAB(n1, n2);
_multMod(mod, eq);
}
// HOW TO USE ::
// -- set correct maxBase
// -- use mult(n1, n2), multMod(n1, n2, mod) and multLL(n1, n2)
// -- input : A[], B[]
// -- output : C[]
}
const int MX = (1<<17);
ll p2[MX] , fact[MX] , invfact[MX];
int n , arr[MX];
int MOD = 1e9 + 7;
ll POW(ll x , ll y){
if(y == 0) return 1;
ll ret = POW(x , y/2);
ret *= ret; ret %= MOD;
if(y % 2) ret *= x;
return ret % MOD;
}
int main(){
int T;
cin>>T;
p2[0] = fact[0] = 1;
for(int j = 1 ; j < MX ; j++){
p2[j] = 2 * p2[j-1]; p2[j] %= MOD;
fact[j] = j * fact[j-1]; fact[j] %= MOD;
}
for(int j = 0 ; j < MX ; j++)
invfact[j] = POW(fact[j] , MOD - 2);
while(T--){
scanf("%d",&n);
for(int j = 1 ; j <= n ; j++){
scanf("%d",&arr[j]);
}
//sort(arr+1,arr+1+n);
for(int i = 0 ; i < MX ; i++){
fft::A[i] = 0;
fft::B[i] = 0;
}
for(int j = 1 ; j <= n ; j++){
fft::A[j] = 1ll * (((1ll * p2[n - j] * fact[j - 1])%MOD) * arr[j])%MOD;
}
for(int j = 0 ; j <= n ; j++){
fft::B[j] = invfact[n - j];
}
fft::mult(n + 2 , n + 2 , MOD , 0);
for(int j = 1 ; j <= n ; j++){
ll theta = fft::C[n + j];
theta *= invfact[j-1];
theta %= MOD;
printf("%lld ",theta);
}
puts("");
}
}