51nod 1835 完全图

原题链接.
比赛时我怎么都不会做这一题。旁边人表过了。

显然的状态是$f_{i,j}$表示用了序号前i个，有j块的方案数。

显然可以枚举第i个放的块的大小来转移。

$f_{i,j} =\sum_{k=1}^{i-(j-1)}f_{i-k,k-1}*f_{k-1,1}*C_{i-1}^{k-1}$

这条方程神奇之处在于自我调用$f_{k-1,1}$。

但是这条方程显然是不能转移j=1的情况的。

因为$f_{i,1}$如果要转移，会用到$f_{i,1}$本身，就爆了。

一种非常恶心的思路：
$f_{i,1}=2^{n*(n-1)/2} - \sum_{j=2}^{i}f_{i,j}$

……

这是A题，编程挑战一道四级题。

Code：

#include
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;const int mo = 998244353;const int N = 501;int n, m, f[N][N], g[N][N];int ksm(ll x, int y) {ll s = 1;for(; y; y /= 2, x = x * x % mo)if(y & 1) s = s * x % mo;return s;
}int main() {fo(i, 0, 500) {g[i][0] = 1;fo(j, 1, i) g[i][j] = (g[i - 1][j] + g[i - 1][j - 1]) % mo;}scanf("%d %d", &n, &m);fo(i, 1, n) {fo(j, 2, i)fo(k, 1, i - j + 1)f[i][j] = (f[i][j] + (ll)f[i - k][j - 1] * f[k][1] % mo * g[i - 1][k - 1] % mo) % mo;f[i][1] = ksm(2, i * (i - 1) / 2);fo(j, 2, i) f[i][1] = (f[i][1] - f[i][j] + mo) % mo;}if(m != 1) printf("%d", f[n][m]); else printf("%d\n", f[n][m] - 1);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！