Description：

已知第 $k$ 个盒子的价格是 $b_k$ ，设 $a[i]$ 为 $i$ 个球的所有球不同盒子相同盒子不空的摆放的花费之和，求 $b[l]\sim b[r]$ 。

$1\leqslant l\leqslant r\leqslant n\leqslant 10^5,r - l\leqslant 100$

Solution：

首先不难发现那个摆放方式是第二类斯特林数，那么： $$ a[i]=\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}b[j] $$ 那么根据斯特林反演： $$ b[i]=\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}a[j] $$ 由于 $r-l\leqslant 100$ ，而我们知道斯特林数一行后可以 $O(n)$ 求下一行，因此我们可以先预处理出一行的值，然后往下递推即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,l,r;

#define MAXN 400010

int fac[MAXN],inv[MAXN];

#define P 1000000007

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

typedef long long ll;

int v[MAXN];

int S[MAXN];

struct comp

{

	long double r,i;

	comp(long double r_ = 0,long double i_ = 0){r = r_;i = i_;}

}a[MAXN],b[MAXN],c[MAXN],d[MAXN];

comp r1[MAXN],r2[MAXN],r3[MAXN];

comp operator + (comp a,comp b){return comp(a.r + b.r,a.i + b.i);}

comp operator - (comp a,comp b){return comp(a.r - b.r,a.i - b.i);}

comp operator * (comp a,comp b){return comp(a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r);}

int rev[MAXN];

const long double PI = acos(-1);

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	return len;

}

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = comp(cos(-type * 2 * PI / i),sin(-type * 2 * PI / i));

		for(int j = 0;j < l;j += i)

		{

			comp w = comp(1,0);

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

void mul(int x[],int y[],int z[],int l)

{

	for(int i = 0;i < l;++i)a[i].i = 0,a[i].r = x[i] & 32767;

	for(int i = 0;i < l;++i)b[i].i = 0,b[i].r = x[i] >> 15;

	for(int i = 0;i < l;++i)c[i].i = 0,c[i].r = y[i] & 32767;

	for(int i = 0;i < l;++i)d[i].i = 0,d[i].r = y[i] >> 15;

	FFT(a,l,1);FFT(b,l,1);FFT(c,l,1);FFT(d,l,1);

	for(int i = 0;i < l;++i)

	{

		r1[i] = a[i] * c[i];

		r2[i] = a[i] * d[i] + b[i] * c[i];

		r3[i] = b[i] * d[i];

	}

	FFT(r1,l,-1);FFT(r2,l,-1);FFT(r3,l,-1);

	for(int i = 0;i < l;++i)

	{

		int da = ll(r1[i].r + 0.5) % P;

		int db = ll(r2[i].r + 0.5) % P;

		int dc = ll(r3[i].r + 0.5) % P;

		z[i] = (da + ((ll)db << 15) % P + ((ll)dc << 30) % P) % P;

	}

	return;

}

int f[30][MAXN];

int v0[MAXN],v1[MAXN],v2[MAXN],v3[MAXN],v4[MAXN],v5[MAXN];

void calc(int l,int d)

{

	f[d][0] = 1;

	if(l & 1){f[d][0] = l - 1;f[d][1] = 1;}

	if(l == 1 || l == 0)return;

	int n = l / 2;

	calc(n,d + 1);

	for(int i = 0;i <= n;++i)v0[n - i] = 1ll * f[d + 1][i] * fac[i] % P * power(n,i) % P;

	for(int i = 0;i <= n;++i)v4[i] = inv[i];

	int len = init(l);

	mul(v0,v4,v5,len);

	for(int j = 0;j <= n;++j)v2[j] = 1ll * v5[n - j] * inver(power(n,j)) % P * inv[j] % P;

	mul(v2,f[d + 1],v1,len);

	for(int i = 0;i <= l;++i){v3[i] = 0;for(int j = 0;j <= 1;++j)v3[i] = (v3[i] + 1ll * v1[i - j] * f[d][j] % P) % P;}

	for(int i = 0;i <= l;++i)f[d][i] = v3[i];

	return;

}

int t[MAXN];

int s[MAXN];

int main()

{

	scanf("%d%d%d",&n,&l,&r);

	fac[0] = 1;for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	inv[n] = power(fac[n],P - 2);for(int i = n - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	calc(l - 1,0);

	for(int i = 0;i <= l - 1;++i)t[i] = f[0][i];

	for(int i = 1;i <= n;++i)scanf("%d",&v[i]);

	for(int i = l - 1;i <= r;++i)

	{

		if(i != l - 1)for(int j = i;j >= 0;--j)t[j] = (t[j - 1] + 1ll * t[j] * (i - 1) % P) % P;

		for(int j = 0;j <= i;++j)s[i] = (s[i] + 1ll * (((i - j) & 1) ? P - 1 : 1) * t[j] % P * v[j] % P) % P;

	}

	for(int i = l;i <= r;++i)printf("%d ",(s[i] - s[i - 1] + P) % P);

	cout << endl;

	return 0;

}