0x50「动态规划」例题
这类问题可能常用到的相关知识：容斥原理，组合数递推，乘法逆元（用于计算组合数），快速幂。
计数类DP
为了保证DP计数过程中的不重不漏，这一类DP问题往往会有些特殊的“子结构”或者说是“阶段”，我们的原则是——找到一个“基准点”，围绕它构造一个“不可分割”的整体，避免子问题重叠。
例题
POJ1737 Connected Graph
状态表示：F[i]表示i个节点的无向连通图有多少个
设计转移方程时，我们考虑将1号点作为基准点。首先用容斥原理考虑，n个点的无向图连通图个数=n个点的无向图个数-n个点的无向不连通图。其中，任意两个点之间可以建边，总共最多可建条边，每条边可以有两种选择：连接或断开。因此n个点的无向图个数是
。考虑计算n个点的无向不连通图的方案数，由于一个无向不连通图必然由多个连通块构成，于是设1号点所在的连通块的大小为j，那么从2...n这n-1个点中选出j-1个点与1号点构成连通块的方案数是
，剩下的点随意组合，方法数为
。
转移方程：，其中
且
边界：
目标：
由于n较小，可直接用帕斯卡公式递推组合数，双重循环DP，时间复杂度：
PS：本题因为答案很大，所以需要高精度，用这个公式实现高精度，需要维护高精度加法，高精度减法，高精度乘法，高精度低精度乘法，高精度快速幂五种操作。于是，代码中method_1是不含高精度的，method_2是含有高精度，但是使用的直接递推（非容斥原理），代码如下
/*
*/
#define method_2
#ifdef method_1
/*
n>9时int溢出
https://blog.csdn.net/icefox_zhx/article/details/79055962
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int INF=0x3f3f3f3f;
int n,c[maxn][maxn],f[maxn];
void pre1(){
c[0][0]=1;
for(int i=1;i<=50;i++){
for(int j=0;j<=i;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
}
void pre2(){
f[1]=1,f[2]=1,f[3]=4;
for(int i=3;i<=50;i++){
f[i]=(1<<c[i][2]);
for(int j=1;j<=i-1;j++){
f[i]-=f[j]*(1<<c[i-j][2])*c[i-1][j-1];
}
}
}
int main() {
ios::sync_with_stdio(false);
freopen("Connected Graph.in","r",stdin);
pre1();
pre2();
while(cin>>n&&n){
cout<<f[n]<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int maxl=400+5;
const int INF=0x3f3f3f3f;
ll n,c[maxn][maxn],bin[maxn];
struct bigint{
ll a[maxl],n;
bigint(){memset(a,0,sizeof(a)),n=0;}
ll& operator[](int x){return a[x];}
void print(){for(int i=n;i>=1;i--) cout<<a[i];}
friend bigint operator+(bigint x,bigint y){
bigint res;res.n=max(x.n,y.n);
for(int i=1;i<=res.n;i++) res[i]=x[i]+y[i];
for(int i=1;i<=res.n;i++) res[i+1]+=res[i]/10,res[i]%=10;
if(res[res.n+1]) res.n++;
return res;
}
friend bigint operator*(bigint x,bigint y){
bigint res;res.n=x.n+y.n-1;
for(int i=1;i<=x.n;i++) for(int j=1;j<=y.n;j++)res[i+j-1]+=x[i]*y[j];
for(int i=1;i<=res.n;i++) res[i+1]+=res[i]/10,res[i]%=10;
while(res[res.n+1]) res.n++,res[res.n+1]+=res[res.n]/10,res[res.n]%=10;
return res;
}
friend bigint operator*(bigint x,ll y){
bigint res;res.n=x.n;
for(int i=1;i<=x.n;i++) res[i]+=x[i]*y;
for(int i=1;i<=res.n;i++) res[i+1]+=res[i]/10,res[i]%=10;
while(res[res.n+1]) res.n++,res[res.n+1]+=res[res.n]/10,res[res.n]%=10;
return res;
}
}f[maxn];
void pre1(){
c[0][0]=1;
bin[0]=1;
for(int i=1;i<=50;i++){
bin[i]=bin[i-1]<<1;
for(int j=0;j<=i;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
}
void pre2(){
f[1][1]=1,f[1].n=1,f[2][1]=1,f[2].n=1;
for(int i=3;i<=50;i++){
for(int j=1;j<=i-1;j++){
f[i]=f[i]+f[i-j]*f[j]*c[i-2][j-1]*(bin[j]-1);
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Connected Graph.in","r",stdin);
pre1();
pre2();
while(cin>>n&&n){
f[n].print();E;
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
POJ1037 A Decorative Fence
由于要求排名C的栅栏的形状，所以用类似数位DP中的常用手段——试填法。具体地说，我们从小到大枚举第一块木板的高度，若后面n-1块木板的排名小C则继续循环，同时令C减去第一块高度为len的方案数。若后面n-1块木板的排名大于等于C则第一块木板的高度就应该是C，这是试填成功，break出当前循环，继续试填下一块木板。为了高效计算，我们预处理出当第一块木板高度确定时，剩下所有木板构成的方案数。
状态表示：F[i,j,k]表示i块长度不同的木板，最左边木板长度从小到大排在第j位，位置状况为k（k=0表示处于低位，k=1表示处于高位）的方案数。
设计转移方程时，由于高低位相间，所以阶段i和阶段i-1之间构成重叠子问题，使得DP原理合法。
转移方程：
PS：这个转移方程里有一点格外重要，即p的范围问题。首先，若最左边的木板高度上排在第j位，同时处于低位。那么它的前一块木板必然处于高位，并且其高度排名大于等于j，注意这里是大于等于的原因在于去掉最左边的木板时，所有高度排名大于它的木板的高度排名都会-1，而所有高度小于它的木板的高度排名不变，所以才出现了p可以取到j的情况。而若最左边的木板若是处于高位，那么去掉它之后，下一个处于低位的木板的排名必然严格小于j。
PPS：第一块木板可能既处于高位，也可能处于低位，所以单独处理。
边界：
目标：准备拼凑答案状态，方法已在上面讲过，这里不再赘述
三重循环DP，时间复杂度：，其中试填法复杂度：
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+5;
const int INF=0x3f3f3f3f;
int T,n,used[maxn];
ll m,f[maxn][maxn][2];
void pre(){
f[1][1][0]=f[1][1][1]=1;
for(int i=2;i<=20;i++){
for(int j=1;j<=i;j++){
for(int k=1;k<=j-1;k++){
f[i][j][1]+=f[i-1][k][0];
}
for(int k=j;k<=i-1;k++){
f[i][j][0]+=f[i-1][k][1];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("A Decorative Fence.in","r",stdin);
pre();
cin>>T;
while(T--){
cin>>n>>m;
memset(used,0,sizeof(used));
int last,k;
for(int j=1;j<=n;j++){
if(f[n][j][1]>=m){
last=j,k=1;
break;
}
else m-=f[n][j][1];
if(f[n][j][0]>=m){
last=j,k=0;
break;
}
else m-=f[n][j][0];
}
cout<<last<<" ";
used[last]=1;
for(int i=2;i<=n;i++){
k^=1;
int j=0;
for(int len=1;len<=n;len++){
if(used[len]) continue;
j++;
if((k==0&&len<last)||(k==1&&len>last)){
if(f[n-i+1][j][k]>=m){
last=len;
break;
}
else m-=f[n-i+1][j][k];
}
}
cout<<last<<" ";
used[last]=1;
}
cout<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
数位统计DP
数位DP往往是通过预处理DP，然后通过类似倍增DP中的拼凑思想——“试填法”求解。（例题：POJ 3208、BZOJ 1799）
