[hihocoder1489][微软预科生计划编程笔试][Legendary Items]

好久不更了。。菜鸡还是要打ACM。。来博客拔一拔草（水题求不喷

题目链接

大意就是给一个初始获得奖励的概率P

做任务可以使概率增加Q

于是每做完一个任务就有一个概率X

如果X已经是100%就获得奖励，否则有1−x的概率得不到，要继续做任务

如果这次拿到了奖励那么概率变为⌊P2l⌋%,其中l是当前已经获得的奖励个数

现在要求获得N次奖励的期望完成任务数

N≤106,P≤100,Q≤100

那么期望的计算式可以写成Ei=Σpk∗lk,其中pk表示做了lk个任务后拿到i个奖励的概率

用Pi表示⌊P2i⌋%

接着考虑Ei+1=Σp′k∗l′k

=Pi+1∗Σpk∗(lk+1)

+(1−Pi+1)∗(Pi+1+Q%)∗Σpk∗(lk+2)

+(1−Pi+1)∗(1−Pi+1−Q%)∗(Pi+1+2Q%)∗Σpk∗(lk+3)+...

直到Pi+1+kQ%超过1结束

于是用ci=Σpk

Ei+1=Σp′k∗l′k

=Pi+1∗(Ei+ci)

+(1−Pi+1)∗(Pi+1+Q%)∗(Ei+2ci)

+(1−Pi+1)∗(1−Pi+1−Q%)∗(Pi+1+2Q%)∗(Ei+3ci)+...

每次计算的次数不会超过100,复杂度上界为O(100N)

注意当i≥8的时候Pi为0,如果在i很大的时候直接计算Pi会出问题

#include <bits/stdc++.h>using namespace std;#define pb push_back#define pii pair<int, int>#define mp make_pair#define ull unsigned long long#define null NULL#define sc(x) scanf("%d", &x)#define sc64(x) scanf("%I64d", &x)#define scln(x) scanf("%d\n", &x)#define sc64ln(x) scanf("%I64d\n", &x)#define pr(x) printf("%d", x)#define prln(x) printf("%d\n", x)#define prsp(x) printf("%d ", x)#define pr64(x) printf("%I64d", x)#define pr64ln(x) printf("%I64d\n", x)#define pr64sp(x) printf("%I64d ", x)#define rep(i,n) for (int i = 1;i <= (n); ++i)#define repr(i,n) for (int i = (n);i > 0; --i)#define repab(i,a,b) for (int i = a;i <= b; ++i)#define Rep(i,n) for (int i = 0;i < (n); ++i)#define Repr(i,n) for (int i = (n)-1;i >= 0; --i)#define Repab(i,a,b) for (int i = a;i < b; ++i)#define SET(__set, val) memset(__set, val, sizeof __set)typedef long double ld;typedef long long ll;typedef pair<ll, ll> pll;template<class T> T gcd(T a, T b){if(!b)return a;return gcd(b,a%b);}template<class T> T power(T a, T b){T res(1);while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;}template<class T> T powerM(T a, T b, T mod){T res(1);while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}const int infi = 2147483647;const ll infl = 9223372036854775807;#define N 1111000#define M 1000int n, m, k;double f[N], c[N];int main(){double p, q, p1, p2;sc(m), sc(k), sc(n);p1 = p = m, q = k;p2 = 1.0;p1 /= 100;f[1] = 0.0;rep(i,100){f[1] += (p1*p2)*i;c[1] += p1*p2;if (p1 == 1)break;p2 *= 1-p1;p1 += q/100;if (p1 > 1)p1 = 1;}repab(i,2,n){if (i >= 8)p1 = 0;elsep1 = floor(p/(1<<(i-1)))/100.0;p2 = 1.0;f[i] = 0.0;rep(j,100){f[i-1] += c[i-1];f[i] += p1*p2*f[i-1];c[i] += p1*p2;if (p1 == 1)break;p2 *= 1-p1;p1 += q/100;if (p1 > 1)p1 = 1;}}printf("%.2lf\n", f[n]);return 0;}