标签：20241003 int res long 当前 dp mod

缩进优化

我们可以枚举 \(i\) 的所有倍数,我们让每一块中的数除以 \(i\) 相等,显然这是调和集数

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e7 + 5, INF = 1e18;

int n, a[N], sum[N], ans = INF, cnt[N];

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum[a[i]] += a[i];
    cnt[a[i]]++;
  }
  for (int i = 1; i <= 2000000; i++) {
    sum[i] += sum[i - 1];
    cnt[i] += cnt[i - 1];
  }
  for (int i = 1; i <= 1000000; i++) {
    int tmp = 0;
    for (int j = 0; j <= 1000000; j += i) {
      tmp += (sum[j + i - 1] - sum[max(0ll, j - 1)]) - (j * (cnt[j + i - 1] - cnt[max(0ll, j - 1)]));
      tmp += (j / i) * (cnt[j + i - 1] - cnt[max(0ll, j - 1)]);
    }
    ans = min(ans, tmp);
  }
  cout << ans;
  return 0;
}

外星人

首先如果 \(x \mod a = res\) 那么 \(res \mod b (b >= a) = res\),所以我们可以直接将 \(a_i\) 送大到小排序,我们设 \(dp_{i, j}\) 表示当前选到了第 \(i\) 个数,当前的数字为 \(j\) ,那么如果考虑当前这个数不选就是 \(dp_{i, j} += dp_{i - 1, j} \times (n - i)\) 因为当前这个数可以放到后面的 \(n - i\) 个位置 ,如果考虑当前这个数选,那么就是 \(dp_{i, {j \mod a_i}} += dp_{i - 1, j}\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

int n, x, a[N], dp[N][N];

bool cmp(int _x, int _y) {
  return _x > _y;
}

signed main() {
  cin >> n >> x;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1, cmp);
  dp[0][x] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= x; j++) {
      dp[i][j % a[i]] += dp[i - 1][j];
      dp[i][j % a[i]] %= mod;
      dp[i][j] += (dp[i - 1][j] * (n - i) % mod);
      dp[i][j] %= mod;
    }
  }
  int ans = x;
  while (!dp[n][ans]) {
    ans--;
  }
  cout << ans << "\n" << dp[n][ans];
  return 0;
}

标签：20241003,int,res,long,当前,dp,mod
From： https://www.cnblogs.com/libohan/p/18445968