标签：20241014 frac int long times ans mod

子集和问题（subset）

由于是子序列,所以选的顺序没有要求,那么我们可以从大到小排序,然后设 \(dp_{i, j}\) 表示选前 \(i\) 个中的数字,和为 \(j\),然后每次统计时直接乘上组合数即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e3 + 5, mod = 998244353;

int n, m, a[N], dp[N], cur[N], ans[N];

int fact[N], inv[N], factinv[N];

int C(int n, int m) {
  return fact[n] * factinv[m] % mod * factinv[n - m] % mod;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  freopen("subset.in", "r", stdin);
  freopen("subset.out", "w", stdout);
  fact[0] = 1, inv[1] = 1, factinv[0] = 1;
  for (int i = 1; i <= 3000; i++) {
    fact[i] = fact[i - 1] * i % mod;
    if (i > 1) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    factinv[i] = factinv[i - 1] * inv[i] % mod;
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  dp[0] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j <= m; j++) {
      cur[min(j + a[i], m)] += dp[j];
      cur[min(j + a[i], m)] %= mod;
    }
    for (int j = 0; j < i; j++) {
      ans[j] += C(i - 1, j) * cur[m] % mod;
      ans[j] %= mod;
    }
    for (int j = 0; j <= m; j++) {
      dp[j] += cur[j];
      dp[j] %= mod;
      cur[j] = 0;
    }
  }
  for (int i = 0; i <= n; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}

完美挑战（perfect）

我们考虑直接将无限的式子列出来,接下来是只考虑一个数的情况

\[t \times \frac {a}{b} + t \times (1 - \frac {a}{b}) + t \times \frac {a}{b} \times (1 - \frac {a}{b}) + t \times (1 - \frac {a}{b}) ^ 2 + t \times \frac {a}{b} \times (1 - \frac {a}{b}) ^ 2 ... \]

那么我们可以化简成

\[t \times \frac {a}{b} \times (1 + (1 - \frac {a}{b}) + (1 - \frac {a}{b}) ^ 2...) + t \times (1 - \frac {a}{b}) \times (1 + (1 - \frac {a}{b}) + (1 - \frac {a}{b}) ^ 2...) \]

然后用等比数列化简,然后再用类似于一战到底的方法排序即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 5, mod = 998244353;

struct node {
  int t, a, b;
}x[N];

int n, ans;

long double val(node i, node j) {
  long double ans = i.t + i.t * (i.b - i.a) * 1.0 / i.a * 1.0;
  ans = (ans + j.t) + (ans + j.t) * (j.b - j.a) * 1.0 / j.a * 1.0;
  return ans;
}

bool cmp(node _x, node _y) {
  return val(_x, _y) < val(_y, _x);
}

int mypow(int a, int b) {
  int tot = 1;
  while (b) {
    if (b & 1) {
      tot = tot * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return tot;
}

signed main() {
  freopen("perfect.in", "r", stdin);
  freopen("perfect.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i].t >> x[i].a >> x[i].b;
  }
  //cout << val(x[2], x[1]) << "\n";
  sort(x + 1, x + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    int tmp = (ans + x[i].t) % mod + (ans + x[i].t) * (x[i].b - x[i].a) % mod * mypow(x[i].a, mod - 2) % mod;
    ans = tmp % mod;
  }
  cout << ans;
  return 0;
}

标签：20241014,frac,int,long,times,ans,mod
From： https://www.cnblogs.com/libohan/p/18468409