莓在执行任务时,收集到了 n 份岩浆能源, 其中第 i 份的能量值是 wi ,她
决定将它们分成恰好 k 组带回基地,每一组都要有至少 1 份能源。
每一组能源会对运输设备产生负荷值,若该组有 x 份能源,这 x 份能源能
量值之和为 y , 则产生的负荷值为 x × y 。
每种分组方案产生的负荷是每一组能源产生的负荷值总和,莓想知道所有可
能的分组方案产生的负荷之和对 998244353 取模的结果。
constint N = 1e6 + 5, MOD = 998244353; int n, k, sum, fac[N], ifac[N];
intfpow(int a, int b){ int res = 1; for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) res = res * 1ll * a % MOD; return res; } intC(int n, int k){ if (k > n) return0; return fac[n] * 1ll * ifac[k] % MOD * 1ll * ifac[n - k] % MOD; } intS(int n, int k){ int res = 0; for (int i = 0; i <= k; i++) { int g = (i & 1) ? -1 : 1; g = g * 1ll * fpow(k - i, n) % MOD * C(k, i) % MOD; g = (g + MOD) % MOD; res = (res + g) % MOD; } res = res * 1ll * ifac[k] % MOD; return res; }
intmain(){ freopen("ichigo.in", "r", stdin); freopen("ichigo.out", "w", stdout); scanf("%d %d", &n, &k); for (int i = 1, x; i <= n; i++) scanf("%d", &x), sum = (sum + x) % MOD; fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % MOD; ifac[n] = fpow(fac[n], MOD - 2); for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % MOD; printf("%lld\n", sum * 1ll * (S(n, k) * 1ll + (n - 1) * 1ll * S(n - 1, k) % MOD) % MOD); return0; }
constint N = (3e5 + 9) * 30; int n, x, a[N], tr[N][2], tot; longlong inv[33], dir[33], s[N];
voidinsert(constint &x){ int u = 0; for (int i = 31; i + 1; i--) { int c = ((x >> i) & 1); if (!tr[u][c]) tr[u][c] = ++tot; u = tr[u][c]; s[u]++; } } voidqry(constint &x){ int u = 0; for (int i = 31; i + 1; i--) { int c = ((x >> i) & 1); if (c == 0) inv[i] += s[tr[u][1]]; if (c == 1) dir[i] += s[tr[u][0]]; u = tr[u][c]; } }
intmain(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), insert(a[i]), qry(a[i]); longlong res = 0; int x = 0; for (int i = 0; i <= 31; i++) { if (inv[i] > dir[i]) x |= (1 << i), res += dir[i]; else res += inv[i]; } printf("%lld %d\n", res, x); return0; }