51Nod-1835-完全图

ACM模版

描述

题解

最近懒了好多,写题少了好多,闲来无事水一发……

DPDP 问题,设 dp[i][j]dp[i][j] 表示前 ii 个点形成 jj 个连通块的方案数,具体细节看官方题解吧,不难理解。懒得写 LatexLatex 表达式了……

代码

#include <iostream>

using namespace std;

typedef long long ll;

const int MOD = 998244353;
const int MAXN = 555;

int n, m;
int dp[MAXN][MAXN];
int C[MAXN][MAXN];

ll QPow(ll x, ll n)
{
    ll ret = 1;
    ll tmp = x % MOD;

    while (n)
    {
        if (n & 1)
        {
            ret = (ret * tmp) % MOD;
        }
        tmp = tmp * tmp % MOD;
        n >>= 1;
    }

    return ret;
}

void init()
{
    for (int i = 0; i < MAXN; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

int main(int argc, const char * argv[])
{
    init();

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2; j <= i; j++)
        {
            for (int k = 1, t = i - j + 1; k <= t; k++)
            {
                dp[i][j] = (dp[i][j] + (ll)dp[i - k][j - 1] * dp[k][1] % MOD
                         * C[i - 1][k - 1] % MOD) % MOD;
            }
        }
        dp[i][1] = (int)QPow(2, i * (i - 1) >> 1);
        for (int j = 2; j <= i; j++)
        {
            dp[i][1] = (dp[i][1] - dp[i][j] + MOD) % MOD;
        }
    }

    printf("%d\n", m != 1 ? dp[n][m] : dp[n][m] - 1);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-2096-Collecting Bugs

    ACM模版 描述 ? image.png image.png 代码 #include <iostream> #include <cstdio> using n...

    f_zyj
  • HDU-6004-Periodical Cicadas

    ACM模版 描述 ? image.png image.png 代码 #include <iostream> #include <algorithm> usin...

    f_zyj
  • HDU-6249-Alice’s Stamps

    ACM模版 描述 ? 题解 DPDP 问题,设 dp[i][j]dp[i][j] 表示前 ii 个位置选取 jj 个区间的最优解。当然 ii 要加以处理,因为我...

    f_zyj
  • LintCode 背包问题II题目分析

    给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

    desperate633
  • 蓝桥杯省内模拟赛C++

    问题描述   将LANQIAO中的字母重新排列,可以得到不同的单词,如LANQIAO、AAILNOQ等,注意这7个字母都要被用上,单词不一定有具体的英文意义。...

    杨鹏伟
  • 01背包及其变种(物品无限背包、恰好装满背包)

    一、01背包问题   01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解将那...

    用户1215536
  • Backpack problem

    AngelNH
  • 【剑指Offer】60. n个骰子的点数

    使用一个二维数组 dp 存储点数出现的次数,其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

    瑞新
  • 1163 访问艺术馆

     时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description     皮尔...

    attack
  • 87. [NOIP2000] 乘积最大

    ★☆   输入文件:cjzd.in   输出文件:cjzd.out 简单对比 时间限制:1 s   内存限制:128 MB   问题描述 今年是国际...

    attack

扫码关注云+社区

领取腾讯云代金券