No Abstracts.

Now I have abstracts.

Damn it! Useless IBus, now I cannot input Chinese!

Des.

Click Here

Sol.

First we make $f[i]$ as the probability of hit $i$ times among $k$ times in a round. We can also get the probability of getting 1 life point back.

So we get $p[i][j]$ as the probability of changing life points from $i$ to $j$ in one round.

Then we can list the expectation of answers when our target have $i$ points left. That is:

Notice that when one has $n$ points, he cannot get life increased.

As we deal the expression, we would find that all expectations only have to do with $E_1$ and $E_2$, so we can calculate the factor before $E_1$ and $E_2$ for each $i$ in range $[1,n]$.

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;
typedef long long ll;

const int maxn = 1505;

int n, k, m, P;
ll f[maxn], p[maxn][maxn], a[maxn], b[maxn];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % mod;
    index >>= 1;
    base = base * base % mod;
  }
  return ret;
}
inline void inc(ll &lhs, const ll &rhs) {
  lhs += rhs;
  if (lhs >= mod) lhs -= mod;
}

int main() {
  int T = rd();
  while (T--) {
    n = rd(); P = rd(); m = rd(); k = rd();
    if (!k) {
      puts("-1");
      continue;
    }
    if (m == 0) {
      int rnd = 0;
      if (k == 1) puts("-1");
      else {
        while (P > 0) rnd++, P = min(n, P + 1) - k;
        printf("%d\n", rnd);
      }
      continue;
    } 
    for (int i = 0; i <= n; ++i)
      f[i] = 0;
    ll Inv_mpls = quick_power(m + 1, mod - 2);
    f[0] = 1;
    int lim = min(n - 1, k);
    for (int i = 1; i <= lim; ++i)
      f[i] = f[i - 1] * quick_power(i, mod - 2) % mod 
             * (k - i + 1) % mod;
    for (int i = 0; i <= lim; ++i)
      f[i] = f[i] * quick_power(m, k - i) % mod
             * quick_power(quick_power(m + 1, k), mod - 2) % mod;
    if (k >= n) {
      f[n] = 1;
      for (int i = 0; i < n; ++i)
        f[n] = (f[n] - f[i] + mod) % mod;
    }
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= n; ++j)
        p[i][j] = 0;
    for (int i = 1; i < n; ++i)
      for (int j = 1; j <= i + 1; ++j)
        inc(p[i][j], (Inv_mpls * f[i - j + 1] + 
                     m * Inv_mpls % mod * f[i - j]) % mod);
    for (int i = 1; i <= n; ++i)
      inc(p[n][i], f[n - i]);
    for (int i = 0; i <= n; ++i)
      a[i] = b[i] = 0;
    a[1] = 1;
    for (int i = 1; i < n; ++i) {
      ll suma = a[i], sumb = (b[i] - 1 + mod) % mod;
      for (int j = 1; j <= i; ++j)
        suma = (suma - p[i][j] * a[j] % mod + mod) % mod;
      for (int j = 1; j <= i; ++j)
        sumb = (sumb - p[i][j] * b[j] % mod + mod) % mod;
      ll inv = quick_power(p[i][i + 1], mod - 2);
      a[i + 1] = suma * inv % mod;
      b[i + 1] = sumb * inv % mod;
    }
    ll suma = a[n], sumb = (1 - b[n] + mod) % mod;
    for (int i = 1; i <= n; ++i) {
      suma = (suma - p[n][i] * a[i] % mod + mod) % mod;
    }
    for (int i = 1; i <= n; ++i) {
      sumb = (sumb + p[n][i] * b[i]) % mod;
    }
    ll x = 1ll * sumb * quick_power(suma, mod - 2) % mod;
    ll ans = (a[P] * x + b[P]) % mod;
    printf("%lld\n", ans);
  }
  return 0;
}