DP IV

BB

太久没更新了冒个泡！ QAQ
抽了最近感觉有些意思的dp题来写
下次更新应该又是猴年马月 QAQ

Natasha, Sasha and the Prefix Sums - CodeForces 1204E

Description
求所有由n个1和m个-1组成的序列的最大前缀和之和，结果对998244853取模
0 <= n, m <= 2000
Sample Input

0 2
2 0
2 2
2000 2000

Sample Output

0
2
5
674532367

Solution - 类似卡特兰数 + DP
2400不会系列QAQ
定义DP状态dp(i, j)为有i个1和j个-1的答案，那么
dp(i,j) = dp(i - 1, j) + C(i + j - 1, i - 1) + dp(i, j - 1) - (C(i + j - 1, i) - f(i, j - 1))
其中f(i, j)为有i个1和j个-1时最大前缀和为0的方案数
如何理解？
对于已有的方案，
① 可以在 前面 放1，此时最大前缀和一定变大1，这些方案有C(i + j - 1, i - 1)个，这部分贡献为dp(i - 1, j) + C(i + j - 1, i - 1)
② 可以在 前面 放-1，此时最大前缀和若大于0，则一定减小1，这部分方案有C(i + j - 1, i) - f(i, j - 1)个，若为0则保持不变
接下来要处理的问题是如何计算f(i, j)，有
f(i, j) = f(i - 1, j) + f(i, j - 1), i <= j
对于已有方案，可以选择在最后面放1或-1，都不会使得最大前缀和超过0，因为前面的最大前缀和受DP状态约束，而最后一次的前缀和为i - j <= 0
Tips：卡特兰数的推论中提到了 f(i, j) = C(i + j, j) - C(i + j, j + 1)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int N = (int)2000 + 15;
const int inf = 0x3f3f3f3f;
const int MOD = 998244853;

int f[N][N], dp[N][N], mul[N << 2], invMul[N << 2];

inline int addMod(int a, int b) {
  return a + b >= MOD ? a + b - MOD : a + b;
}

inline int quickPow(int a, int b) {
  int ans = 1, base = a;
  while(b) {
    if(b & 1) {
      ans = (ll)ans * base % MOD;
    }
    base = (ll)base * base % MOD;
    b >>= 1;
  }
  return ans;
}

inline int comb(int n, int m) {
  return n >= m ? (ll)mul[n] * invMul[m] % MOD * invMul[n - m] % MOD : 0;
}

inline void init() {
  mul[0] = invMul[0] = 1;
  for(int i = 1; i < (N << 2); i++) {
    mul[i] = (ll)mul[i - 1] * i % MOD;
    invMul[i] = quickPow(mul[i], MOD - 2);
  }
}

int main() {
  init();

  for(int y = 1; y < N; y++) {
    f[0][y] = 1;
  }
  for(int x = 1; x < N; x++) {
    for(int y = x; y < N; y++) {
      f[x][y] = addMod(f[x - 1][y], f[x][y - 1]);
    }
  }

  for(int x = 1; x < N; x++) {
    dp[x][0] = x;
    for(int y = 1; y < N; y++) {
      dp[x][y] = addMod(addMod(dp[x - 1][y], comb(x + y - 1, x - 1)), addMod(dp[x][y - 1], MOD - addMod(comb(x + y - 1, x), MOD - f[x][y - 1])));
    }
  }

  int n, m;
  while(~scanf("%d%d", &n, &m)) {
    printf("%d\n", dp[n][m]);
  }
}


Mysterious Code - Codeforces 1163D

Description
定义f(s, t)为t串在s串中的出现次数
给定串c, s, t，其中c串中可能出现*字符，每一个*都必须替换为任意一个字符（小写字母），问f(c, s) - f(c, t)
s, t只包含小写字母，且长度不超过50，c串长度不超过1000
Sample Input

*****
katie
shiro

caat
caat
a

*a*
bba
b

***
cc
z

Sample Output

1
-1
0
2

Solution - KMP + DP
因为问的是次数，所以可以考虑用KMP预处理串s, t，得到next数组 定义dp状态为dp(i, j, k)，代表当串c匹配到第i位时，串s在next状态j下，串t在next状态k下的答案，那么通过枚举i, j, k，向前转移状态，最终答案为 max{dp(n, j, k)}，其中n为串c的长度

#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int N = (int)1000 + 15;
const int MOD[2] = {(int)1e9 + 7, 1234567891};
const int SIZE = 26;
const int inf = 0x3f3f3f3f;

struct KMP {
    char s[N];
    int nxt[N];

    void getNext() {
        nxt[1] = 0;
        int i = 1, j = 0;
        while(s[i]) {
            if(j == 0 || s[i] == s[j]) {
                i++;
                j++;
                nxt[i] = j;
            } else {
                j = nxt[j];
            }
        }
    }

    int move(int len, char ch) {
        int pos = len;
        if(s[pos + 1] == 0) {
            pos = nxt[pos];
        }
        for(; pos && s[pos] != ch; pos = nxt[pos]);
        return pos;
    }
};

KMP ss, st;
char sc[N];
int dp[N][52][52];

int main() {
    while(~scanf("%s%s%s", sc + 1, ss.s + 1, st.s + 1)) {
        memset(dp, 0x80, sizeof(dp));
        dp[0][0][0] = 0;
        ss.getNext();
        st.getNext();
        int p = strlen(sc + 1), n = strlen(ss.s + 1), m = strlen(st.s + 1);
        for(int i = 0; i < p; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < m; k++) {
                    if(dp[i][j][k] == (int)0x80808080) {
                        continue;
                    }
                    if(sc[i + 1] != '*') {
                        int nj = ss.move(j + 1, sc[i + 1]);
                        int nk = st.move(k + 1, sc[i + 1]);
                        dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + (j + 1 == n && ss.s[j + 1] == sc[i + 1]) - (k + 1 == m && st.s[k + 1] == sc[i + 1]));

                    } else {
                        for(char ch = 'a'; ch <= 'z'; ch++) {
                            int nj = ss.move(j + 1, ch);
                            int nk = st.move(k + 1, ch);
                            dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + (j + 1 == n && ss.s[j + 1] == ch) - (k + 1 == m && st.s[k + 1] == ch));
                        }
                    }
                }
            }
        }

        int ans = -inf;
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < m; k++) {
                ans = max(ans, dp[p][j][k]);
            }
        }
        printf("%d\n", ans);
    }
}


Steps to One - Codeforces 1139D

Description
给定一个空数组和一个数m (1 < m <= 100000)
每次随机从[1, m]中随机选择一个整数，将其加入数组中，直到数组内的数的gcd为1
问数组的期望长度
Sample Input

1
2
4

Sample Output

1
2
333333338

Solution - DP + 莫比乌斯反演
这题可能别的题解更简单，这里谈谈本菜鸡的做法QAQ （伪 · DP） 设dp(i, k)为k | gcd时的概率，则显然dp(i, k) = dp(i - 1, k) * ceil(m / k) / m，dp(0, k) = 1，那就没有dp的必要性了，直接写成dp(i, k) = (ceil(m / k) / m) ^ i，当k >= 2时，期望长度为sum((i + 1) * dp(i, k))，这里i + 1是因为要在末尾加一个数使得gcd = 1，而这个数带来的概率与期望暂时不计算，在最后再计算
设f(k) = sum((i + 1) * dp(i, k)) = sum((i + 1) * (ceil(m / k) / m) ^ i)，设a = 1 / (m / ceil(m / k))，故f(k) = sum((i + 1) / a^i)，对齐展开可得下两式
f(k) = 2 / a^1 + 3 / a^2 + 4 / a^3 + ...
af(k) = 2 / a^0 + 3 / a^1 + 4 / a^2 + ...
裂项相消，得
(a - 1)f(k) = 2 / a^0 + 1 / a^1 + 1 / a^2 + 1 / a^3 + ...
(a - 1)f(k) = 1 + a / (a - 1)
f(k) = (2a - 1) / (a - 1)^2
设h(k)为gcd = k时的期望，则h(1) = 1 / m，f(k) = h(k) + h(2k) + ...，用莫比乌斯反演求出h(x) = sum{ k = 1 -> m / x, mu(k) * f[x * k] }，这样便可求出h(k)
最后计算期望，需要把最后那个导致gcd = 1的数也算入其中
设g(k) = sum { x = 1 -> m, [gcd(x, m) = 1] }，再来一波反演（省略过程了），可得g(k) = sum( d: d | k, mu(d) * ceil(m / d) )，因此g(k)可以在nlogn时间内预处理掉
最后Answer = h(1) + sum(h(k) * g(k) / m)

// scanf printf push_back emplace_back memset sizeof
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = (int)1e5 + 15;
const ll inf = (ll)1e12;
const int MOD = (int)1e9 + 7;

int mu[N];
bool isprime[N];
int prime[N], tot;
int g[N], inv[N], f[N];

inline int addMod(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

inline int quickPow(int a, ll b) {
  int ans = 1, base = a;
  while(b) {
    if(b & 1) {
      ans = 1LL * ans * base % MOD;
    }
    base = 1LL * base * base % MOD;
    b >>= 1;
  }
  return ans;
}

void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i++) {
        inv[i] = (ll)(MOD - MOD / i) * inv[MOD % i] % MOD;
    }

    memset(isprime, true, sizeof(isprime));
    tot = 0, mu[1] = 1;
    for(int i = 2; i < N; i++){
        if(isprime[i]){
            prime[tot++] = i;
            mu[i] = MOD - 1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j++){
            isprime[i * prime[j]] = false;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }else{
                mu[i * prime[j]] = MOD - mu[i];
            }
        }
    }
}


int main() {
    init();
    int m;
    while(~scanf("%d", &m)) {
        memset(g, 0, sizeof(g));
        for(int d = 1; d <= m; d++) {
            for(int k = d; k <= m; k += d) {
                g[k] = addMod(g[k], 1LL * mu[d] * (m / d) % MOD);
            }
        }
        for(int k = 1; k <= m; k++) {
            int a = 1LL * m * inv[m / k] % MOD;
            f[k] = 1LL * addMod(addMod(a, a), MOD - 1) % MOD * quickPow(addMod(a, MOD - 1), 2LL * MOD - 4) % MOD;
        }
        int ans = inv[m];
        for(int x = 2; x <= m; x++) {
          int sum = 0;
          for(int k = 1; k <= m / x; k++) {
            sum = addMod(sum, 1LL * mu[k] * f[x * k] % MOD);
          }
          ans = addMod(ans, 1LL * sum * g[x] % MOD * inv[m] % MOD);
        }
        printf("%d\n", ans);
    }
}