HDU 5829 Rikka with Subset

题意： 给一个数组A[n], 要求出所有的T[k]，T[i]指A数组的所有子集中前k大的和的和。 虽然只是用FFT的原理，NTT的模板。 将代码中的A和B卷积，然后再乘上，各自对应的系数1/（2……k*(k-1）！）； 需要需用：费马小定理，费马素数 FFT等等。 代码： #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<cstring> #include<map> #include<queue> #include<stack> #include<string> #include<cstdlib> #include<ctime> #include<set> #include<math.h> using namespace std; typedef long long ll; const int nn = 400100; const int inf = (1 << 31); const ll mod = 998244353; const ll g = 3;//mod的原根，当且仅当 g^(MOD-1) = 1 % MOD #define pb push_back #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 ll n,m,q; ll a[nn]; ll inv[nn];//i的阶乘的倒数%mod ll fac[nn]; //i的阶乘 ll f[nn];//记录答案 ll A[nn];//2^(n-i)/i!; ll B[nn];//i!*a[i+1]; ll inv2; ll ppow(ll x, ll n) { ll ans = 1; while (n) { if (n & 1) ans = ans*x%mod; x = x*x%mod; n >>= 1; } return ans; } void init() { inv2 = ppow(2ll, mod - 2); inv[1] = inv[0] = 1; fac[0] = fac[1] = 1; for (ll i = 2; i <= 1e5; i++) { inv[i] = inv[i - 1] * ppow(i, mod - 2)%mod; fac[i] = fac[i - 1] * i%mod; } } void rader(ll y[], ll len) { for (ll i = 1, j = len / 2; i < len-1; i++) { if (i < j) swap(y[i], y[j]); ll k = len / 2; while (j >= k) { j -= k; k /= 2; } if (j < k)j += k; } } void ntt(ll y[], int len, int on) { rader(y, len); for (int h = 2; h <= len; h <<= 1) { ll wn = ppow(g, (mod - 1) / h); //****// if (on == -1) wn = ppow(wn, mod - 2); for (int j = 0; j < len; j += h) { ll w = 1; for (int k = j; k < j + h / 2; k++) { ll u = y[k]; ll t = w * y[k + h / 2] % mod; y[k] = (u + t) % mod; y[k + h / 2] = (u - t + mod) % mod; w = w * wn % mod; } } } if (on == -1) { ll t = ppow(len, mod - 2); for (int i = 0; i < len; i++) y[i] = y[i] * t % mod; } } bool cmp(ll x, ll y) { return x > y; } int main() { int t; scanf("%d", &t); init(); while(t--) { scanf("%lld", &n); memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); memset(a, 0, sizeof(a)); for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1, a + n + 1,cmp); for (ll i = 0; i < n; i++) A[i] = inv[i] * ppow(2, n-i) % mod; for (ll i = 1; i <= n; i++) B[i] = fac[i - 1] * a[i] % mod; reverse(B + 1, B + n + 1); for (ll i = 0; i < n; i++) B[i] = B[i + 1]; B[n] = 0; ll len = 1; while (len <= n * 2)len <<= 1; ntt(A, len, 1); ntt(B, len, 1); for (ll i = 0; i < len; i++) A[i] = A[i] * B[i] % mod; ntt(A, len, -1); ll r = inv2; for (ll i = 1; i <= n; i++) { f[i] = r*inv[i - 1] % mod*A[n - i] % mod; f[i] = (f[i] + f[i - 1]) % mod; printf("%lld ", f[i]); r = r*inv2%mod; } puts(""); } return 0; }