QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#743#488847#8815. Space StationFffooooFffooooFailed.2024-07-24 16:32:042024-07-24 16:32:05

詳細信息

Extra Test:

Invalid Input

input:

55

output:


result:

FAIL Unexpected character #10, but ' ' expected (stdin, line 1)

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488847#8815. Space StationFffooooAC ✓356ms18268kbC++142.8kb2024-07-24 15:44:012024-07-30 16:54:04

answer

#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }
/*

*/
#define ll long long
const int N = 128;
const int mod = 998244353;
int n, m, a[N];
int dp[N][N * N * 2];

ll fpow(ll x, int y) { ll ans = 1; while(y) { if( y & 1 ) ans = ans * x % mod; x = x * x % mod; y >>= 1; } return ans; }
int Inv(const int x) { return fpow(x, mod - 2); }

int fac[N], inv_fac[N];
void init_fac() {
	fac[0] = 1; for(int i = 1; i < N; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
	inv_fac[N - 1] = Inv( fac[N - 1] );
	for(int i = N - 2; i >= 0; --i) inv_fac[i] = (ll)(i + 1) * inv_fac[i + 1] % mod;
}
int C(const int x, const int y) {
	if( x < y ) return 0;
	if( ! y ) return 1;
	return (ll)fac[x] * inv_fac[y] % mod * inv_fac[x - y] % mod;
}

int mian() {
	scanf("%d%d", &n, &m);
	int sum = 0;
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum += a[i];
	dp[0][0] = 1;
	for(int k = n; k; --k) 
		for(int i = n; i; --i) for(int j = sum; j; --j) 
				if( j >= a[k] ) dp[i][j] = ( dp[i][j] + dp[i - 1][ j - a[k] ] ) % mod;
	init_fac();
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		const ll now = Inv( C(n, i) );//|S|=n, |T|=i 
		for(int j = 1; j <= sum; ++j) {
			if( j > i * m ) ans += now * m % mod * dp[i][j] % mod;
			else ans += now * j % mod * Inv(i) % mod * dp[i][j] % mod;
			ans %= mod;
		}
	}
	printf("%d", ans);
	return 0;
} /*
3 3
2 3 4

给定 $n$ 个数字,每一次可以使用 $m$ 或者与这个数字相同的代价抵挡这个数字 
求在不知道这 $n$ 个数字的顺序(但是一旦抵挡就知道了这一个数字)的情况下最小期望花费 
$n\le 100, a_i\le 200$
$2s, 1G$

首先一次操作使用 $m$ 的条件是 $m\le \dfrac{\sum_{i\in S} a_i}{|S|}$ ,$S$ 剩余集合 
(平均数的原因是原本可以看成 $\sum \min(m, a_i)$,加上一个期望过后,那么也是求和,但是变为了平均数。可以理解为代价是求和而不是 $土1$) 
考虑 $dp$,设 $f(S)$ 表示还有 $S$ 的集合中的数字未出现的最小期望代价  
那么转移就是 $f(S)=\min(m,\dfrac{\sum_{i\in S} a_i}{|S|})+\dfrac{1}{|S|}\sum f(S-{a_i})$ ,就是先选择是否抵挡,然后从没有这一个转移
考虑优化。
考虑任意一个集合 $T\sub S$ 对于 $S$ 的贡献(只考虑第一步,否则可能算重),那么就是 $\dfrac{(|S|-|T|)!}{|S|(|S|-1)...(|T|+1)}\times\min(m,\dfrac{\sum_{i\in T} a_i}{|T|})$
就是不断上面的系数中的后一项不断地 $\dfrac{1}{|S|}$,这里不断减小,但是这些数字之间又有顺序,所以阶乘
整理一下就是 $\dfrac{1}{(^{|S|}_{|T|})}\times\min(m,\dfrac{\sum_{i\in T} a_i}{|T|})$
后面一项直接设计 $dp$ 维护后一项,就是设计 `dp[i][j]` 表示当集合的大小是 $i$ 时,总和是 $j$ 的方案数。类似背包转移即可
*/