题面

LOJ #6432. 「PKUSC2018」真实排名

注意排名的定义 , 分数不小于他的选手数量 !!!

题解

有点坑的细节题 ...

思路很简单 , 把每个数分两种情况讨论一下了 .

假设它为 \(x\) .

不对它进行翻倍操作 :
那么很容易发现 \(\displaystyle [\lceil \frac{x}{2}\rceil, x)\) 的数都不翻倍 . 其余部分任意 . 假设有 \(tot\) 个 .
那么这部分答案就是 \(\displaystyle \binom {n-tot - 1} {k}\) .
\(-1\) 因为它本身不能操作 .
对它进行翻倍操作 :
那么又是显然的 , \(\displaystyle [x,2x)\) 的所有数都需要翻倍 . 其余部分任意 . 假设这段有 \(tot\) 个 .
那么这部分答案就是 \(\displaystyle \binom {n - tot}{k - tot}\) .

然后当 \(x=0\) 的时候需要特殊判断 , 我们可以随意翻倍都不改变结果了 , 答案就是 \(\displaystyle \binom {n} {k}\) .

以后做这种题一定不能偷懒 , 用脑子想 , 而是要用笔去写 , 把每种情况写清楚了 !!!

那样并不浪费时间 , 反而节省时间 !!

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

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

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

#endif

}

const int N = 1e5 + 1e3, Mod = 998244353;

int n, k, a[N], b[N];

typedef long long ll;

ll fac[N], ifac[N];

ll fpm(ll x, ll power) {

	ll res = 1; x %= Mod;

	for (; power; power >>= 1, (x *= x) %= Mod)

		if (power & 1) (res *= x) %= Mod;

	return res;

}

ll C(int n, int m) {

	if (n < 0 || m < 0 || n < m) return 0;

	return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;

}

void Init(int maxn) {

	fac[0] = ifac[0] = 1;

	For (i, 1, maxn) fac[i] = fac[i - 1] * i % Mod;

	ifac[maxn] = fpm(fac[maxn], Mod - 2);

	Fordown (i, maxn - 1, 1) ifac[i] = ifac[i + 1] * (i + 1) % Mod;

}

inline int Sum(int l, int r) {

	if (l > r) return 0;

	return upper_bound(a + 1, a + 1 + n, r) - lower_bound(a + 1, a + 1 + n, l);

}

int main () {

	File(); Init(1e5);

	n = read(); k = read();

	For (i, 1, n) a[i] = b[i] = read();

	sort(a + 1, a + 1 + n);

	For (i, 1, n) {

		if (!b[i]) { printf ("%lld\n", C(n, k)); continue ; }

		ll res = C(n - Sum((b[i] + 1) / 2, b[i] - 1) - 1, k);

		int tot = Sum(b[i], b[i] * 2 - 1);

		(res += C(n - tot, k - tot)) %= Mod;

		printf ("%lld\n", res);

	}

    return 0;

}

displaystyle

LOJ #6432. 「PKUSC2018」真实排名(组合数)

题面

题解

代码