【NOIP2019模拟2019.9.4】B（期望的线性性）

题目描述：

\(1<=n,ai<=5*10^5\)

题解：

我是弱智我不会期望线性。

设\(E(a[i])\)表示第i个期望被减的个数。

\(E(a[1])=a[1]\)

不难发现\(E(a[i])(i>1)\)之间互不影响，其实这很难。

考虑固定这两个，它们两个选到的概率一样，选到其它的就无视就好了。

那么只用考虑\(n=2\)的情况，这个直接暴力枚举\(a[1]\)结束时\(a[i]\)有几个，乘个\(1\over 2\)的几次方和组合数，式子如下：

\(=a[i]-\sum_{i=0}^{a[i]-1}C_{a[1]-1+i}^{a[i]-1}*{1\over2}^{a[1]+i}*(a[i]-i)\)

可以用递推的方法依次求出\(a[i]=1,2,3…\)的答案。

时间复杂度：\(O(n+max(a))\)

Code：

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

using namespace std;

const int mo = 323232323;

ll ksm(ll x, ll y) {

	ll s = 1;

	for(; y; y /= 2, x = x * x % mo)

		if(y & 1) s = s * x % mo;

	return s;

}

const ll ni2 = ksm(2, mo - 2);

const int N = 1e6 + 5;

int n, a[N];

ll fac[N], nf[N], a2[N];

void build(int n) {

	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;

	nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;

	a2[0] = 1; fo(i, 1, n) a2[i] = a2[i - 1] * ni2 % mo;

}

ll C(int n, int m) {

	return fac[n] * nf[m] % mo * nf[n - m] % mo;

}

ll f[N], g[N];

int main() {

	freopen("b.in", "r", stdin);

	freopen("b.out", "w", stdout);

	scanf("%d", &n);

	fo(i, 1, n) scanf("%d", &a[i]);

	build(1e6 + 2);

	fo(i, 0, 5e5) {

		if(i) f[i] = f[i - 1], g[i] = g[i - 1];

		f[i] = (f[i] + a2[a[1] + i] * C(a[1] + i - 1, i)) % mo;

		g[i] = (g[i] + a2[a[1] + i] * C(a[1] + i - 1, i) % mo * i) % mo;

	}

	ll ans = a[1];

	fo(i, 2, n) {

		ans += a[i];

		ans -= (f[a[i] - 1] * a[i] - g[a[i] - 1]) % mo;

	}

	ans = (ans % mo + mo) % mo;

	pp("%lld\n", ans);

}

巴特西

【NOIP2019模拟2019.9.4】B（期望的线性性）

题目描述：

题解：

Code：

最新文章

热门文章