Dylan's Blog

POJ1737 Connected Graph [计数类DP]

Posted on 2018-08-10 Edited on 2022-06-05 In 题解

问题描述：

问你包含$n$个节点的无向联通图有多少个，其中节点的编号为$1-n$

输入：

有多组数据，输入以0结束每组数据一个整数$n$表示有$n$个节点（$n<=50$）

输出：

每组数据一行，表示有$n$个节点的无向联通图的个数

思路：

计数类DP好难啊。。。根本想不到。。。

我们设$f[i]$为：包含$i$个节点的无向联通图的个数，那么答案就是$f[n]$。然后这个可以等价为所有无向图总数-无向不联通图的个数。无向图总数很容易求，为$2^{n*(n-1)/2}$，而无向不联通图的个数可以通过DP得到。

假设我们推出了$f[1]$到$f[i-1]$，我们现在要求包含$i$个节点的无向不联通图个数。我们设1号节点所在的联通大小为$j$，那么这个联通块就有$C_{i-1}^{j-1}$种选择节点的方案，对于每一种选择方案，联通块有$f[j]$种构成方法，并且联通块之外的点是可以任意连边的的，所以有$2^{(i-j)*(i-j-1)/2}*f[j]$种情况。于是最后我们可以得出转移方程： $f\[i\]=2^{i\*(i-1)/2}-\\sum\_{j=1}^{i-1} 2^{(i-j)\*(i-j-1)/2}\*f\[j\]$

最后也是最最毒瘤的一点就是这道题要用高精！！！

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define MAXN 2505
#define LL long long
using namespace std;

int n;
string f[MAXN], pow[MAXN];

string add(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]+=numy[i];
        numx[i+1]+=numx[i]/10, numx[i]%=10;
    }
    if(numx[maxl]) maxl++;
    for(int i=maxl-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string sub(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]-=numy[i];
        if(numx[i]<0) numx[i]+=10, numx[i+1]--;
    }
    while(numx[--maxl]==0 && maxl>0) ;
    for(int i=maxl; i>=0; i--) ans+=numx[i]+'0';
    return ans;

}

string mul(string x, string y)
{
    string ans;
    int numx[500]={0}, numy[500]={0}, numz[500]={0};
    int lenx=x.length(), leny=y.length();
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxlen=lenx+leny-1;
    for(int i=0; i<lenx; i++)
        for(int j=0; j<leny; j++) numz[i+j]+=numx[i]*numy[j];
    for(int i=0; i<maxlen; i++) numz[i+1]+=numz[i]/10, numz[i]%=10;
    if(numz[maxlen]) maxlen++;
    for(int i=maxlen-1; i>=0; i--) ans+=numz[i]+'0';
    return ans;
}

string div(string x, LL b)
{
    string ans;
    int lenx=x.length(), d=0;
    for(int i=0; i<lenx; i++)
    {
        ans+=(d*10+x[i]-'0')/b+'0';
        d=(d*10+(x[i]-'0'))%b;
    }
    for(int i=0; i<ans.size(); i++)
        if(ans[i]!='0') return ans.substr(i);
    return "0";
}

string change(LL x)
{
    string ans;
    int numx[500], lenx=0;
    while(x)
    {
        numx[lenx++]=x%10;
        x/=10;
    }
    for(int i=lenx-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string comb(LL n, LL m)
{
    string sum="1";
    for(LL i=m+1; i<=n; i++) sum=mul(sum, change(i));
    for(LL i=1; i<=n-m; i++) sum=div(sum, i);
    return sum;
}

int main()
{
    pow[0]="1";
    for(int i=1; i<=1500; i++) pow[i]=mul(pow[i-1], change(2));
    for(int i=1; i<=50; i++)
    {
        f[i]=pow[i*(i-1)/2];
        for(int j=1; j<i; j++)
        {
            string temp="";
            temp=mul(mul(comb(i-1, j-1), f[j]), pow[(i-j)*(i-j-1)/2]);
            f[i]=sub(f[i], temp);
        }
    }
    while(scanf("%d", &n) && n) cout<<f[n]<<'\n';
}

POJ3613 Cow Relays [矩阵加速递推+最短路]

Posted on 2018-08-08 Edited on 2022-06-05 In 题解

问题描述：

给你一张由$T$条边构成的无向图，求起点$S$到终点$E$恰好经过$N$条边的最道路。（路径可以重复经过）

输入：

第一行包含4个整数$N$、$T$、$S$、$E$ （$N<=1000000，T<=100$，节点编号不超过1000）接下来T行每行三个数$Len，I_1，I_2$ 表示$I_1 I_2$间有一条长度为$Len$的无向边

输出：

一个整数，起点$S$到终点$E$恰好经过$N$条边的最道路长度

思路：

将这个与矩阵加速递推联系起来确实需要对递推有很深的理解（需要很大脑洞）。。。

其实我们每进行一次递推就是多经过一条路径，然后每一次进行递推时都需要将所有点之间的距离初始化一下（如果不初始化就是普通的最短路，初始化了就是经过N条边的最短路）。

我们的递推可以利用类似Floyd的方式来实现。如果直接开$1000*1000$的矩阵复杂度显然会爆掉，于是我们考虑只有100条边，那么最多只有200个点是有用的，因此我们先离散化一下。最后按照套路利用矩阵快速幂优化一下递推就能够过了。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int n, m, t, s, e, tot, sub[205], f[205][205], g[205][205];

struct A {int s, t, len;} a[205];

void mul(int x[205][205], int y[205][205])
{
    int ans[205][205];
    memset(ans, 0x3f, sizeof(ans));
    for(int k=1; k<=m; k++)
        for(int i=1; i<=m; i++)
            for(int j=1; j<=m; j++)
                ans[i][j]=min(ans[i][j], x[i][k]+y[k][j]);
    memcpy(x, ans, sizeof(ans));
}

int main()
{
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d%d%d", &n, &t, &s, &e);
    sub[++tot]=s; sub[++tot]=e;
    for(int i=1; i<=t; i++)
    {
        scanf("%d%d%d", &a[i].len, &a[i].s, &a[i].t);
        sub[++tot]=a[i].s; sub[++tot]=a[i].t;
    }
    sort(sub+1, sub+tot+1);
    m=unique(sub+1, sub+tot+1)-sub-1;
    for(int i=1; i<=t; i++)
    {
        int x=lower_bound(sub+1, sub+m+1, a[i].s)-sub;
        int y=lower_bound(sub+1, sub+m+1, a[i].t)-sub;
        f[x][y]=min(f[x][y], a[i].len);
        f[y][x]=min(f[y][x], a[i].len);
    }
    memcpy(g, f, sizeof(g));
    n--;
    while(n)
    {
        if(n&1) mul(g, f);
        mul(f, f); n>>=1;
    }
    s=lower_bound(sub+1, sub+m+1, s)-sub;
    e=lower_bound(sub+1, sub+m+1, e)-sub;
    printf("%d\n", g[s][e]);
}

BZOJ3037 创世纪 [基环树+树形DP]

Posted on 2018-08-07 Edited on 2022-06-05 In 题解

问题描述：

上帝手中有着N 种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。

帝希望知道他最多可以投放多少种世界元素，你需要帮助上帝解决这个问题。

输入：

第一行是一个整数$N$，表示世界元素的数目。第二行有$N$个整数$A_1, A_2, …, A_N$。$A_i$ 表示第$i $个世界元素能够限制的世界元素的编号。

输出：

一个整数，表示最多可以投放的世界元素的数目。

思路：

根据题意，我们可以发现限制关系是一个环加内向树森林，这道题就是一个基环树森林版本的“没有上司的舞会”。因此，这道题的DP转移方程很容易推出，难就难在如何处理基环树森林。

关于基环树上的树形DP我们在BZOJ1791 Island这题中提到过，用的是找出环然后破环为链的方法。然而这道题用这个方法就不好处理，于是我们可以用分类讨论，进行两次DP的方法处理。我们对于每棵基环树找出环上的任意一条边，先假设不用这条边的限制，那么就是一个直接的树形DP，为了方便我们把所有边反着建，把边所在的一个端点作为根节点，然后这样得出了答案一。再假设这条边的限制一定要用到，也是同样的DP只是要一个特判，这样得出的答案二。那么最终的答案就是两个答案中大的那一个。

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAXN 1000006
using namespace std;

int n, cnt, ans, root, fa[MAXN], head[MAXN], f[MAXN][2];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt; 
}

int find(int x)
{
    if(vis[x]) return x;
    vis[x]=1;
    return find(fa[x]);
}

void dfs(int x, int fa)
{
    f[x][0]=f[x][1]=0; vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        dfs(to, fa);
        f[x][0]+=max(f[to][0], f[to][1]);
    }
    if(x==fa) {f[x][1]=f[x][0]+1; return;}
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        f[x][1]=max(f[x][1], f[x][0]-max(f[to][1], f[to][0])+f[to][0]+1);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &fa[i]);
        addedge(fa[i], i);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])
        {
            root=find(i);
            dfs(root, 0);
            int temp=max(f[root][0], f[root][1]);
            dfs(root, fa[root]);
            temp=max(f[root][0], temp);
            ans+=temp;
        }
    printf("%d\n", ans);
}

CF559C Gerald and Giant Chess [计数类DP]

Posted on 2018-08-07 Edited on 2022-06-05 In 题解

问题描述：

给你一个$h*w$的网格，其中有$n$个黑色的格子，它们的位置为$(x_i, y_i)$。你从左上角开始，每一步只能向左或者下移动，并且不能经过黑色格子，问你有多少种到达右下角的方案。

输入：

第一行给你三个数$h, w, n$（$1<=h, n<=10^5, 1<=n<=200$）

输出：

输出对$10^9+7$取模的方案数

思路：

感觉JXOI很喜欢考计数类DP，然而自己菜的一比。。。

首先我们就是要考虑如何设计一个状态，能够统计DP时的信息，并且能够根据这个状态不重不漏地进行DP（我觉得计数类DP就是这个难，状态转移反而容易一些）。因为黑色格子不多，所以我们的复杂度应该和黑色的格子有关。我们可以先将黑色格子按照横纵坐标排序，然后设$f[i]$为到达$i$个黑色格子且不经过前$i-1$个黑色格子的可能路径数。特别的，设$f[n+1]$的坐标为$(h+1, w+1)$，那么答案就是$f[n+1]$了。

接下来我们考虑如何计算和转移。我们可以先计算出到达第$i$个黑色格子所有路径，这个的数量为$C_{x_i+y_i-2}^{x_i-1}$，原因是一共要向下或向左走$x_i+y_i-2$步，然后其中要任选$x_i-1$步向左走。然后还要减去经过前面黑色格子的路径数，因此我们可以推出DP方程为: $f\[i\]=C\_{x-i+y\_i-2}^{x\_i-1}-\\sum\_{j=0}^{i-1} f\[j\]\*C\_{x\_i+y\_i-x\_j-y\_j}^{x\_i-x\_j}$ 还要特别注意的是如果$x_j>x_i$或者$y_j>y_i$时，这一项是不用减去的。

代码：

#include <bits/stdc++.h>
#define MAXN 300005
#define p 1000000007
#define LL long long
using namespace std;

int h, w, n;
LL f[MAXN], fac[MAXN], inv[MAXN];

struct Node {int x, y;} a[MAXN];

bool CMP(Node x, Node y)
{
    if(x.x==y.x) return x.y<y.y;
    else return x.x<y.x;
}

LL comb(LL n, LL m)
{
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

void init()
{
    inv[0]=fac[0]=fac[1]=inv[1]=1;
    for(int i=2; i<=MAXN-5; i++)
    {
        fac[i]=(fac[i-1]*i)%p;
        inv[i]=inv[p%i]*(p-p/i)%p;
    }
    for(int i=2; i<=MAXN-5; i++) inv[i]=(inv[i]*inv[i-1])%p;
}

int main()
{
    init();
    scanf("%d%d%d", &h, &w, &n);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    a[n+1].x=h; a[n+1].y=w;
    for(int i=1; i<=n+1; i++)
    {
        f[i]=comb(a[i].x+a[i].y-2, a[i].x-1);
        for(int j=1; j<i; j++)
        {
            if(a[j].x>a[i].x || a[j].y>a[i].y) continue;
            f[i]=(f[i]-f[j]*comb(a[i].x+a[i].y-a[j].x-a[j].y, a[i].x-a[j].x))%p;
        }
    }
    printf("%lld\n", (f[n+1]+p)%p);
}

Codeforces24D Broken robot [概率期望DP+高斯消元]

Posted on 2018-08-07 Edited on 2022-06-05 In 题解

问题描述：

在$N*M$的网格中有一个起始位置为$(x, y)$的robot。它每一步会随机的执行四个操作中一个：待在原地，向左，向右，向下（它是不能够移动到网格之外的）。然后问你它移动到第$N$行的步数期望值为多少。

输入：

第一行两个整数$N，M$，表示$N*M$的网格（$1<=n, m<=1000$）第二行两个整数$x，y$，表示起始位置为$(x, y)$

输出：

输出到第$n$行的期望步数

思路：

这道题中的状态转移方程并不难想到。但是我们发现这些状态会相互影响，并且无法推出其中的任何一个。对于这种期望DP就要用到另一种套路“高斯消元”。

按照套路我们依然从后往前推，第$n$行的所有期望值都为0，我们把这个作为初值向前DP。对于每一行我们都能根据转移方程列出一个方程组，而且我们发现其中的每个方程只有2-3个变量（边界时为两个，其余为3个）。于是我们可以不用普通$O(N^3)$的高斯消元，而是可以YY出一个类似的$O(n)$的消元方法，然后对于每一行都进行一遍这个操作，总复杂度为$O(nm)$。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define MAXN 1005
using namespace std;

int n, m, x, y;
double a[MAXN][5], g[MAXN], f[MAXN], w[MAXN];

void guass()
{
    for(int i=1; i<m; i++)
    {
        double rate=a[i+1][0]/a[i][1];
        a[i+1][0]-=a[i][1]*rate;
        a[i+1][1]-=a[i][2]*rate;
        w[i+1]-=w[i]*rate;
    }
    f[m]=w[m]/a[m][1];
    for(int i=m-1; i>=1; i--) f[i]=(w[i]-a[i][2]*f[i+1])/a[i][1];
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i=1; i<=m; i++)
    {
        g[i]=2;
        if(i>1) g[i]++;
        if(i<m) g[i]++;
        g[i]=1.0/g[i];
    }
    for(int i=n-1; i>=x; i--)
    {
        for(int j=1; j<=m; j++)
        {
            if(j!=1) a[j][0]=-g[j];
            a[j][1]=1-g[j];
            if(j!=m) a[j][2]=-g[j];
            w[j]=g[j]*f[j]+1;
        }
        guass();
    }
    printf("%lf\n", f[y]);
}