ARC144D

考虑 \(x=2^a,y=2^b,a\ne b\) 的情况，有 \(f(x+y)=f(x)+f(y)-f(0)\)。

因此可以归纳到任意情况，令 \(c=f(0),g(i)=f(2^i)-c\)，那么有 \(f(s)=c+\sum\limits_{i\in s}g(i)\)。

所以任意一组 \(\left\{c,g(0),g(1),\cdots,g(n-1)\right\}\) 对应一个 \(f\) 的方案。需要满足 \(0\le c\le k\)，且任意若干个 \(g\) 的和满足 \(\in[-c,k-c]\)。

设 \(g\) 中正数和为 \(s^{+}\)，负数和为 \(s^{-}\)。

则有 \(c+s^{+}\le k,c+s^{-}\ge0\)，移项可得 \(-s^{-}\le c\le k-s^{+}\)，也就是说合法的 \(c\) 的取值有 \(\max(0,k-s^{+}+s^{-}+1)\)，由于 \(s^+-s^-=\sum\left|g_i\right|\)，即 \(\max(0,k-\sum\left|g_i\right|+1)\)。

考虑枚举有几个数非 \(0\)，假设有 \(i\) 个数，那么选的方案数为 \(2^i\binom{n}{i}\)，前面的幂次是枚举每个数的符号，那么接下来就考虑这样一个子问题：
对于 \(i\) 个正整数 \(g_i\) 组成的所有可能的 \(\sum g_i\le k+1\)，对于 \(k+1-\sum g_i\) 求和。

即求出 \(\sum\limits_{x=i}^{k+1}(k+1-x)\binom{x-1}{i-1}\)。

考虑这个东西的组合意义，从 \(k+1\) 个球中选出 \(i+1\) 个球，枚举倒数第二个球的位置 \(x\)，则它右边的球的位置有 \(k+1-x\) 种可能，左边的方案数为从 \(x-1\) 个球中选出 \(i-1\) 个球。

故上面这个式子等于 \(\dbinom{k+1}{i+1}\)。

则答案为

预处理组合数什么的就好了。

时间复杂度 \(\mathcal O(n)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, mod = 998244353;
ll n, k;
ll fac[N], inv[N], u[N];

ll qpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

void init(int maxn) {
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i) fac[i] = fac[i - 1] * i % mod;
	inv[maxn] = qpow(fac[maxn], mod - 2);
	for (int i = maxn - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
	u[0] = 1;
	for (int i = 1; i <= maxn; ++i) u[i] = (k + 1 - i + 1) % mod * u[i - 1] % mod;
}

ll C(ll n, ll m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return fac[n] * inv[n - m] % mod * inv[m] % mod;
}

ll D(ll n) {
	return u[n] * inv[n] % mod;
}

void add(ll &a, ll b) {
	a += b;
	if (a >= mod) a -= mod;
}

int main() {
	scanf("%lld%lld", &n, &k);
	init(n + 1);
	ll ans = 0, w = 1;
	for (int i = 0; i <= n; ++i) add(ans, w * C(n, i) % mod * D(i + 1) % mod), add(w, w);
	printf("%lld", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16855793.html