ARC028 D - 注文の多い高橋商店

Last updated Apr 13, 2022

まず、クエリを無視して計算をします。このときのFPSを$F$とおくと、

$$ \begin{aligned} F &= \prod_{i = 1}^{N} (1 + \cdots + x^{a_i}) \\\ &= \prod_{i = 1}^{N} \frac{1 - x^{a_i + 1}}{1 - x} \\\ &= (1 - x)^{-N} \prod_{i = 1}^{N} (1 - x^{a_i + 1}) \end{aligned} $$

EDPC M - Candiesと同じ式となり$O(NM)$で計算できます。

次に、$k$種類目の商品を抜いて計算することを考える。$k$種類目の商品を抜いた時のFPSを$G_k$とすれば、

$$ \begin{aligned} G_k &= F \frac{1 - x}{1 - x^{a_k + 1}} \\\ &= F (1 + x^{a_k + 1} + x^{2(a_k + 1)} + \cdots) (1 - x) \end{aligned} $$

$1 + x^{a_k + 1} + x^{2(a_k + 1)} + \cdots$は周期$a_k + 1$ごとに累積和を取る操作なので、$G_k$は$O(K)$で求められます。

クエリ$k, x$に対しては$[x^{M - x}]G_k$で答えることができて、全体で$O(NK)$で求められます。

提出コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
i64 N, K, Q;
cin >> N >> K >> Q;
vector<i64> A(N);
rep(i,0,N) {
  cin >> A[i];
  A[i]++;
}

vector<i64> R(Q), C(Q);
rep(i,0,Q) cin >> R[i] >> C[i];
vector<fp> dp(K + 1);
dp[0] = 1;
rep(i,0,N) {
  for(i64 j = K + 1; j --> A[i];) {
    dp[j] -= dp[j - A[i]];
  }
}
rep(i,0,N) {
  rep(j,1,K + 1) {
    dp[j] += dp[j - 1];
  }
}
vector<vector<pair<i64, i64>>> qry(N);
rep(i,0,Q) {
  R[i]--;
  qry[R[i]].push_back( { C[i], i } );
}

vector<fp> ans(Q);

rep(r,0,N) {
  vector<fp> nxt(K + 1);
  vector<fp> sum(A[r]);
  rep(i,0,K + 1) {
    sum[i % A[r]] += dp[i];
    nxt[i] = sum[i % A[r]];
  }
  for(i64 j = K + 1; j --> 1;) {
    nxt[j] -= nxt[j - 1];
  }
  for(auto [c, q]: qry[r]) {
    ans[q] = nxt[K - c];
  }
}
rep(i,0,Q) {
  cout << ans[i] << "\n";
}