概率/期望类Dp列题

一.D - increment of coins (atcoder.jp)

       （1）题目大意

        给定你金银铜牌的数量，每次你能等概率的从里面随机抽取一枚牌，然后放回两枚同样颜色的牌，现在问你，当有某个袋中有一百个牌就不执行操作，问你操作次数的期望。

        （2）解题思路

                很容易想到当100枚币在一块的时候，我们的操作就结束了，因此期望次数为0，因此我们定义dp[a][b][c]为金牌有a，银牌有b，铜牌有c的期望操作次数。因此把每一个状态加上多一个状态的操作次数期望就可以了，最终答案就是dp[a][b][c]。

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
const int N = 101;
double dp[N][N][N];
double f(int a,int b,int c)
{
    if(a == 100 || b == 100 || c == 100) return dp[a][b][c] = 0;
    if(dp[a][b][c] > -1) return dp[a][b][c];
    dp[a][b][c] = 0;
    dp[a][b][c] += (f(a + 1,b,c) + 1.0) * a / (1.0 * a + b + c);
    dp[a][b][c] += (f(a,b + 1,c) + 1.0) * b / (1.0 * a + b + c);
    dp[a][b][c] += (f(a,b,c + 1) + 1.0) * c / (1.0 * a + b + c);
    return dp[a][b][c];
}
void solve()
{
    int a,b,c;
    cin >> a >> b >> c;
    memset(dp,-1,sizeof(dp));
    cout << fixed << setprecision(9) << f(a,b,c) << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) {
        solve();
    }
    return 0;
}

二.Problem - F - Codeforces

        （1）题目大意

        给定你一个序列，有两个操作，第一个操作是把第i个数改为x，第二个操作询问l，r中每个数的数量是否是k的倍数，如果是，则输出YES，否则输出NO。

         （2）解题思路

        对于每个询问我没补可能直接做，套数据结构直接做也是不现实的问题，因为有个带修的操作，因此我们考虑一个概率，我们把原数组里面每个数和查询的数都离散化一下。我们已知一个性质若又区间里面的所有个数都是k的倍数，那么s % k == 0,若我们反过来推，则这个性质不一定成立，但是我们可以多验证40次，每一次失败的概率都是1/2，若我们验证40次，有一次失败，那我们则认为他就是失败的，否则认为他是成功的，那么这样答案不正确的概率仅仅为1/2^40。因此我们需要随机40*N个数，存放到每一次验证中，采用线性同余法生成随机数，对于区间和查询，我们只需要建立40个树状数组即可。

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 3e5 + 10;
long long s[40][N];
int num[40][N],a[N];
int n,q,loc;
struct qry {int op,l,r,x;}qr[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int now,int p,int v)
{
    while(p <= n) {
        s[now][p] += v;
        p += lowbit(p);
    }
}
ll query(int now,int p)
{
    ll res = 0;
    while(p > 0) {
        res += s[now][p];
        p -= lowbit(p);
    }
    return res;
}
unsigned int seed = 1e9+7;
int Random()
{
    seed = (seed << 10) + (seed >> 10) + seed + 1e9 + 7;
    return seed / 2;
}
void solve()
{
    cin >> n >> q;
    vector <int> all;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        all.push_back(a[i]);
    }
    for(int i = 1;i <= q;i++) {
        cin >> qr[i].op;
        if(qr[i].op == 1) {
            cin >> qr[i].l >> qr[i].r;
            all.push_back(qr[i].r);
        }
        else cin >> qr[i].l >> qr[i].r >> qr[i].x;
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    for(int i = 0;i < all.size();i++)
        for(int j = 1;j <= 37;j++)
            num[j][i] = Random();
    for(int i = 1;i <= n;i++) {
        a[i] = lower_bound(all.begin(),all.end(),a[i]) - all.begin();
        for(int j = 1;j <= 37;j++) add(j,i,num[j][a[i]]);
    }
    for(int i = 1;i <= q;i++) {
        if(qr[i].op == 2) {
            bool ok = true;
            for(int j = 1;j <= 37;j++) {
                if((query(j,qr[i].r) - query(j,qr[i].l - 1)) % qr[i].x) {
                    ok = false;
                    break;
                }
            }
            if(!ok) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else {
            qr[i].r = lower_bound(all.begin(),all.end(),qr[i].r) - all.begin();
            for(int j = 1;j <= 37;j++) {
                add(j,qr[i].l,num[j][qr[i].r] - num[j][a[qr[i].l]]);
            }
            a[qr[i].l] = qr[i].r;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) solve();
    return 0;
}