把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

1657E Star MST
题目大意： 给一个点数位n（范围为250）的完全图，每条边边权在k（范围为250）以内，要求最小生成树权值等于从1到其它边的边权数之和的图数量，模998244353。

解：

是经典的k的n次方分配数量问题，限制条件可以转化为对于每个点，1到它的距离大于等于它到所有其它点的距离（否则的话最小生成树就可以连更短的边），因此实际上其它的边我完全不需要记录，我只要一个数组来记录从1到每一个点的距离，以此就能够算出这种情况下图的数量。
N在250以内的数据决定了无法状压，那么怎么办呢？
这里出现了一个在这种问题中非常常用的“解冻法”，假设一共有n个点，一开始从i向n-1遍历，假设最初所有边的权值都为1，每次i的增加过程中我都会解冻一些点，被解冻的点当i+1的时候本身也会+1，冻住的点依然为1。显然在我解冻的时候解冻的那些边权值都还是为1的，那么和他们相连的边的值可以取1到i的任意值，并且由于提前解冻的边已经经过不断次+1，他们的权值肯定会大于新解冻的边，所以实现了无后效性。
这种状态转移的方式巧妙地无视了原本数据的顺序性，可能不是唯一的解法，但是非常无脑。
用dp[i][j]表示遍历到i且有j个点还在冻结时的方案数，最后要求的就是dp[n][0]（为什么是dp[n][0]而不是∑dp[n][i]，不告诉你），起始时，dp[0][n]=1,状态转移的时候从dp[i-1][j]通过遍历j以及这次要解冻的数量k来实现，转移方程是dp[i][j-k]+=dp[i-1][j]*C(n-j,k)*pow(i,边数)，边数的算法通过等差数列实现，复杂度为O(n3)。
硬去想解冻法的实现原理还是很绕的，不过还是建议去把它彻底理解出来，实际上是一种非常实用的算法，或许可以尝试一下把它用在之前的Arena上呢……

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 1000005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
using namespace std;
ll dp[255][255], hzh[255];
ll cp[505][70005];
ll C[255][255];
void initC(const int& n) {
	for (int i = 0; i <= n; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mdl;
	}
}
ll cpow(ll x, ll n) {
	int tmp = n;
	if (cp[x][n] != 0)return cp[x][n];
	ll ans = 1;
	if (n == 0)ans = 1;
	else if (n % 2 == 1) {
		ans = x * cpow(x, n - 1) % mdl;
	}
	else {
		ll a = cpow(x, n / 2);
		ans = a * a % mdl;
	}
	cp[x][n] = ans;
	return ans;
}
inline int tblock(int x, int y) {
	return x* (x - 1) / 2 - (x - y) * (x - y - 1) / 2;
}
int main() {
	cfast;
	initC(254);
	int n, k;
	cin >> n >> k;
	dp[0][n - 1] = 1;
	for (int i = 1; i <= k; i++) {
		inc(a, 0, n) {
			for (int b = 0; b <= a; b++) {
				dp[i][a - b] += (dp[i - 1][a] * C[a][b]) % mdl * cpow(i, tblock(a, b)) % mdl;
				dp[i][a - b] = dp[i][a - b] % mdl;
			}
		}
	}
	cout << dp[k][0];
}