1922. bugaosuni59的SSR---概率dp

 1 

#include 
 2 using namespace std;
 3 
 4 double a[100005], b[100005];
 5 double power(double a, int n) {
 6     double res = 1.0;
 7     for (; n; n >>= 1, a = a * a) {
 8         if (n & 1) res = res * a;
 9     }
10     return res;
11 }
12 int n, k; double p;
13 void solve() {
14     cin >> n >> k >> p;
15     memset(a, 0, sizeof(a));
16     memset(b, 0, sizeof(b));
17     a[0] = 1.0;
18     b[0] = 1.0;
19     for (int i = 1; i <= n; i++) {
20         b[i] = a[i - 1] *(1 - p);
21         if (i < k) a[i] = b[i] + a[i - 1] * p;
22         else a[i] = b[i] + a[i - 1] * p - b[i - k] * power(p, k);
23     }
24     printf("%.4f\n", 1 - a[n]);
25 }
26 int main() {
27     int tt;
28     cin >> tt;
29 
30     
31     while (tt--) {
32         solve();
33     }
34 
35 }