感觉还是好多东西记不得了，gg。

Continue reading →

主要思路

这一道题其实挺好的，我们来分析一下。

首先，我们知道在一个方格纸上，从左上角到右下角的路径的数量是\(C_{H+W-2}^{H-1}\)，可以理解为横向路径的选法总数。之后，我们来进行容斥。在本题中，我们需要容斥掉那些经过了至少一次黑点的路径数量。因为本题中黑点个数小于\(5000\)，所以我们直接来跑一个\(O(n^2)\)的 DP。设\(F[i]\)为经过了此点的路径数，然后我们把右下角的点设为第\(n+1\)个点，最后答案存在\(F[n+1]\)处。我们可以很快得到一个递推式：

\[ F[i] = C_{x_i + y_i – 2}^{x_i – 1} – \sum_{j = 1}^{i-1} (F[j] * C_{x_i-x_j+y_i-y_j}^{x_i-x_j})，且x_i \geq x_j, y_i \geq y_j. \]

解释：对于到点\(i\)的路径，首先不考虑之前的黑点则有\( C_{x_i + y_i – 2}^{x_i – 1} \)种路；而要容斥掉至少经过过一次的黑点的路径，可以直接对于之前的每一个点进行计算，计算之前的点\(j\)到现在的点\(i\)有多少种路径。

代码

// CF559C.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
using namespace std;
const int MOD = 1e9 + 7, MAX_N = 2020, LEVEL_RG = 200000;
ll level[200010], inv[200010], n, h, w, F[MAX_N];
pr pts[MAX_N];
ll quick_power(ll bas, ll tim, ll mod)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll C(ll n, ll m) { return level[n] * inv[n - m] % MOD * inv[m] % MOD; }
int main()
{
    scanf("%d%d%d", &h, &w, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].first, &pts[i].second);
    sort(pts + 1, pts + 1 + n);
    pts[n + 1].first = h, pts[n + 1].second = w;
    level[0] = inv[0] = 1;
    for (int i = 1; i <= LEVEL_RG; i++)
        level[i] = level[i - 1] * i % MOD;
    ll inv_bas = quick_power(level[LEVEL_RG], MOD - 2, MOD);
    for (int i = LEVEL_RG; i >= 1; i--)
        inv[i] = inv_bas, inv_bas = inv_bas * i % MOD;
    for (int i = 1; i <= n + 1; i++)
    {
        F[i] = C(pts[i].first + pts[i].second - 2, pts[i].first - 1) % MOD;
        for (int j = 1; j < i; j++)
            if (pts[j].first <= pts[i].first && pts[j].second <= pts[i].second)
                F[i] = (F[i] - F[j] * C(pts[i].first + pts[i].second - pts[j].first - pts[j].second, pts[i].first - pts[j].first)) % MOD;
    }
    printf("%lld", (F[n + 1] + MOD) % MOD);
    return 0;
}

主要思路

这道题比较有趣，一开始我想出了\(O(n^3)\)的复杂度，打上去 TLE 之后思考前缀做差的方法，但是我太 Naive，不太相信（？）模意义下的减法，所以这个思路在我看了题解之后才搞定。

这道题的 DP 方程不难想到，为：

\[ dp[u][i] = \sum_{t \in dst} \sum_{j \in color(t)} dp[t][j], i \neq j \]

其实我们可以把第二维消掉，考虑总和\(tot[]\)数组，得：

\[ dp[u][i] = \sum_{t \in dst} tot[t] – dp[t][i] \]

然后就出来了。

代码

// P3914.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050, MOD = 1e9 + 7;
int head[MAX_N], current, n, m, tmpx, tmpy, dp[MAX_N][MAX_N], tot[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
    for (int i = 1; i <= m; i++)
    {
        if (!dp[u][i])
            continue;
        for (int e = head[u]; e != -1; e = edges[e].nxt)
        {
            if (edges[e].to == fa)
                continue;
            dp[u][i] = (1LL * dp[u][i] * 1LL * (tot[edges[e].to] - dp[edges[e].to][i])) % MOD;
        }
        while (dp[u][i] < 0)
            dp[u][i] += MOD;
        tot[u] = (1LL * tot[u] + 1LL * dp[u][i]) % MOD;
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmpy);
        for (int j = 1; j <= tmpy; j++)
            scanf("%d", &tmpx), dp[i][tmpx] = 1;
    }
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs(1, 0);
    printf("%d", tot[1] % MOD);
    return 0;
}

Introduction

有的时候我们在日常写题时，会碰见这样的毒瘤 DP 题目，他们一般有以下特性：

• 多维度动态规划
• 循环层数很多，在极限数据下无法 AC。
• 一般出现在区间 DP 中，一般暴力算法复杂度为\(O(n^3)\)。

这个时候我们可以使用单调队列来优化，时间复杂度可以进一步降至\(O(n^2)\)或者是\(O(nm)\)。如果有不会单调队列的同学呢可以去学习以下，顺便可以看看这篇文章：CH1201:最大子序和题解

Overall on this optimization technique

我们来看一道例题：Fence – POJ这道题是一道比较简单的经典 DP。设计状态\(dp[i][j]\)表示前\(i\)个人搞定了前\(j\)个单位的墙。写出方程式：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]+profit_i*(j-k)\}\]

这样的话，整个算法的复杂度是\(O(n^3)\)的。我们能不能将其降为\(O(n^2)\)呢？我们可以把整个方程变个形，之后方程是这样的：

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]-profit_i*k\}+profit_i*j\]

我们发现，这样的话整个方程在\(i\)的循环之下，算是只跟变量\(k\)扯上关系了。我们会发现，只要有\(k_1<k_2\)且\(dp[i-1][k_1]-profit_i*k_1<dp[i-1][k_2]-profit_i*k_2\)，那么就可以直接排除掉答案\(k_1\)。那么就可以使用单调队列来做到这一点。

下面是核心的 DP 代码：

int calc(int i, int k)
{
    return dp[i - 1][k] - wks[i].p * k;
}

// in ( int main() )
for (int i = 1; i <= k; i++)
{
    deque<int> q;
    for (int j = max(0, wks[i].s - wks[i].l); j <= wks[i].s - 1; j++)
    {
        while (!q.empty() && calc(i, q.back()) <= calc(i, j))
            q.pop_back();
        q.push_back(j);
    }
    for (int j = 1; j <= n; j++)
    {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (j >= wks[i].s)
        {
            while (!q.empty() && q.front() < j - wks[i].l)
                q.pop_front();
            if (!q.empty())
                dp[i][j] = max(dp[i][j], calc(i, q.front()) + wks[i].p * j);
        }
    }
}

In Conclusion

整个单调队列优化会为后面的斜率优化做基础（因为我学这个单调队列优化就是有一道题要求使用斜率优化），所以请务必搞懂这个操作。