ferin blog

Sep 1, 2018 - 2 minute read - 競技プログラミング

ARC059 E - キャンディーとN人の子供 / Children and Candies

問題ページ

まず部分点の解法について考える。n=3のときに求めるべき値$f(x_1,x_2,x_3)$を式の形で書いてみる。 $$ x_1^0 \times x_2^0 \times x_3^c
+ x_1^0 \times x_2^1 \times x_3^{c-1}
+ x_1^0 \times x_2^2 \times x_3^{c-2}
\cdots
+ x_1^0 \timex x_2^c \times x_3^0
+ x_1^1 \times x_2^0 \times x_3^{c-1}
+ x_1^1 \times x_2^1 \times x3^{c-2}
\cdots $$ このように考えられるキャンディの割り振り方に対応する積の総和が求めるべき値になる。キャンディの割り振り方を一つずつ試すのはC(n+c-1, n)通りあるため不可能である。状態をうまくもつことで計算量を削減したい。dfs(idx,x) = (idx以降の人に対してx個のキャンディを割り振る場合の値の総和) とすると、$\text{dfs}(idx,x) = \sum
{i=0}^{x} x_idx^i \times \text{dfs}(idx+1,x-i)$ となる。メモ化再起でこの探索はO(NC^2)となる。
満点の解法を考える。上の式ではキャンディの割り振り方を変えていったが満点の制約ではさらにxの値も変化する。これによってdfsの遷移がどのように変化するのか考える。xが変化する分を考慮すると$xidx^i$を掛ける部分が変化し $\text{dfs}(idx,x) = \sum{i=0}^{x} \sum{j=A[idx]}^B{idx] j^i \times \text{dfs}(idx+1,x-i)$ となる。これをそのまま実装するとO(NC^2(B-A))かかってしまい間に合わない。$\sum{j=A[idx]}^B{idx] j^i$ はO(NC(A-B)かけることで事前に計算しておくことができ部分点と同様にO(NC^2)で間に合う。

横着してlogつけたけど普通に間に合った。剰余が多いのでかなり定数倍が重い。

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int p[405][405], memo[405][405];
int n, c;

// idx以降でx個残っているとき
int dfs(int idx, int x) {
  if(memo[idx][x]!=-1) return memo[idx][x];
  if(idx == n-1) return memo[idx][x] = p[idx][x];
  int ret = 0;
  REP(i, x+1) {
    (ret += p[idx][i] * dfs(idx+1, x-i) % MOD) %= MOD;
  }
  return memo[idx][x] = ret;
}

ll binpow(ll x, ll e, ll mo=MOD) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p) % mo; e /= 2;}
    else {a = (a*p) % mo; e--;}
  }
  return a;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> c;
  V<int> a(n), b(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  REP(i, n) {
    REP(j, c+1) {
      FOR(k, a[i], b[i]+1) {
        (p[i][j] += binpow(k, j)) %= MOD;
      }
    }
  }

  memset(memo, -1, sizeof(memo));
  cout << dfs(0, c) << endl;

  return 0;
}