题解：AT_kupc2016_i ティッシュ配り

发现人的最优策略肯定是先一直生成最后再一直发传单，接着发现一个人会生成当且仅当 2c\times i\le 剩下的时间，于是推出最后 n\bmod c 的时间所有人都会发传单，于是把时间每 c 秒分一段就可以直接转化成求 c=1 时的答案。设 f_{i,j} 表示编号为 i 的人只剩 j 的时间最多发多少传单，转移按照之前的结论如果 2i\le j，f_{i,j}\gets f_{i,j-i}+f_{i+1,j-i}，否则 f_{i,j}\gets j，由于还需要计算最后 n\bmod c 发的传单，还需要顺带计算 g_{i,j} 表示这一过程中的总人数。这时复杂度为 O(N^2)，其中 N 为 n 的最大值，但是发现编号为 i 的人最早的出现时间为 \frac{i(i-1)}{2}，所以编号最大值是 O(\sqrt N) 级别的，就没问题了。

代码

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5, B = 450, mod = 1e9 + 7;

int q, dp[B][kMaxN], c[B][kMaxN], t;

inline void A(int &x, int y) { x += y, x >= mod && (x -= mod); }

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  dp[1][0] = 1;
  for (int i = 1; i * (i - 1) / 2 <= 100000; t = i, i++) {
  }
  for (int i = t; i >= 1; i--) {
    for (int j = 0; j + i * (i - 1) / 2 <= 100000; j++) {
      j >= 2 * i ? (dp[i][j] = dp[i + 1][j - i], A(dp[i][j], dp[i][j - i]), c[i][j] = c[i + 1][j - i], A(c[i][j], c[i][j - i]), 0) : (dp[i][j] = j, c[i][j] = 1);
    }
  }
  cin >> q;
  for (int i = 1, n, z; i <= q; i++) {
    cin >> n >> z, cout << (1ll * z * dp[1][n / z] % mod + 1ll * n % z * c[1][n / z]) % mod << '\n';
  }
  return 0;
}