这篇博文主要记录一下学习DP过程中的一些总结（和板子
Ongoing

数位DP

oi-wiki页面
数位DP的格式相对固定，这里放一些做过的题目的代码

上海C题

博客链接
题目链接
要求 ∑ log ⁡ 2 ( i + j ) + 1 \sum \log_2(i+j)+1 ∑log2​(i+j)+1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, X, Y;
const int maxn = 32;
const ll mod = 1e9 + 7;
int xx[maxn], yy[maxn];
int lx, ly;
ll dp[maxn][2][2];

ll solve(int p, bool x, bool y)
{
	if (p == -1)
		return 1ll;
	if (dp[p][x][y] != -1)
		return dp[p][x][y];
	int xlim = x ? 1 : xx[p];
	int ylim = y ? 1 : yy[p];
	ll ans = 0;
	for (int i = 0; i <= xlim; ++i)
	{
		for (int j = 0; j <= ylim; ++j)
		{
			if (i & j)
				continue;
			ans += solve(p - 1, x | (i < xlim), y | (j < ylim));
			ans %= mod;
		}
	}
	dp[p][x][y] = ans;
	return ans;
}

int i2v(int n, int *v)
{
	int i = -1;
	for (; n; n >>= 1)
	{
		i++;
		v[i] = n & 1;
	}
	return i;
}

int main()
{
	// freopen("cin", "r", stdin);
	for (scanf("%d", &t); t--;)
	{
		memset(dp, -1, sizeof(dp));
		memset(xx, 0, sizeof(xx));
		memset(yy, 0, sizeof(yy));
		scanf("%d%d", &X, &Y);
		lx = i2v(X, xx);
		ly = i2v(Y, yy);
		ll ans = 0;
		for (int i = 0; i <= lx; ++i)
			ans = (ans + solve(i - 1, i < lx, i <= ly) * (i + 1)) % mod;
		for (int j = 0; j <= ly; ++j)
			ans = (ans + solve(j - 1, j <= lx, j < ly) * (j + 1)) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}

概率DP

oi-wiki页面
概率DP与传统DP相似度很高，旨在利用选择的无后效性进行状态转移，
主要难度在于如何把递推式推出来
通常用于求期望、求概率（转移的过程中需要用到概率的线性性质，需要些概率论直觉）
目前还没有补过这方面的题，不过个人觉得oi-wiki上的抓老鼠、找bug属于比较典型的题目了
oi-wiki例题「换教室」还没看明白:(