#NOIP模拟赛#相似字符串（树形DP + 状压）

这题是一个状压树DP，有思路可以先想一下，不是特别难（但是我作为一个蒟蒻理解标程看了相当久才彻底想清楚，我的树DP太弱了）

标解写得有点模糊，其实也很清楚，但是我还是想要说一下我对这题思路的理解。

首先是预处理出前缀（我是暴力的，这个可以优化）。题中给出的限制条件很显然是树或者森林。

那么只需要对于有限制的那些点，计算出可能的方案数，其它的可以随便标号。

对于有限制的点，题中限制最多只有16个，用一个int的二进制来表示每一位一定是足够的。

定义Dp[r][S] 表示以r点作为根的子树中，已有标号为状态S的总方案数

对于每一个点，那一位上是0表示这个标号现在不存在（即不在现在这个树中） 1表示在（已经把此树中某点标号）

预先标记出非法的状态，每一个r的转移如下:

假设当前枚举到状态S，那么f[u][S]有两种转移情况

1：S中的1全部标在了r的子树中，那么分成两部分，对于每一棵子树来做，具体看算法一

2：S中的1有一个标在r处，其它的标在子树中，此时枚举限制条件，将前缀标号标在r处。

贴出标解：

Code:（本人代码，由于本人蒟蒻，，就不写C++11那个版本了，因为感觉自己用不上那个？？）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD = 1e9 + 7;

struct ST{
    int len;
    char val[55];
    bool operator < (const ST & X) const{
        return strcmp(val, X.val) < 0;
    }
}S[55];
struct node{
    int v, nxt;
}edge[(1 << 16) + 5];

int N, M, cnt, Ans, All, State;
int A[10], B[10], fa[55], T[20];
int fir[55], Constrait[55];
int Dp[55][(1 << 16) + 5];
bool Avoid[(1 << 16) + 5];

bool getint(int & num){
    char c; int flg = 1;    num = 0;
    while((c = getchar()) < '0' || c > '9'){
        if(c == '-')    flg = -1;
        if(c == -1) return 0;
    }
    while(c >= '0' && c <= '9'){
        num = num * 10 + c - 48;
        if((c = getchar()) == -1)   return 0;
    }
    num *= flg;
    return 1;
}

void addedge(int a, int b){
    edge[++ cnt].v = b, edge[cnt].nxt = fir[a], fir[a] = cnt;
}

void Pre_Work(){
    sort(S, S + N);
    for(int i = 0; i < N; ++ i){
        int MAX = 0;
        for(int j = 0; j < i; ++ j) if(S[i].len > S[j].len){
            bool flg = 1;
            for(int k = 0; k < S[j].len; ++ k)
                if(S[i].val[k] != S[j].val[k]){
                    flg = 0;break;
                }
            if(flg){
                if(MAX < S[j].len)
                    MAX = S[j].len,
                    fa[i + 1] = j + 1;
            }
        }
    }
    memset(fir, -1, sizeof fir );
    for(int i = 1; i <= N; ++ i)
        addedge(fa[i], i);
    State = 0;
    for(int i = 0; i < M; ++ i)//离散化限制条件编号
        T[++ State] = A[i], T[++ State] = B[i];
    sort(T + 1, T + 1 + State);
    State = unique(T + 1, T + 1 + State) - T - 1;
    All = 1 << State;
    for(int i = 0; i < M; ++ i)//对于以Ai为前缀的限制，Constrait[i]表示所有限制的标号（那一位记为1，注意：只要不出现X的前缀是X，那么i这一位是0）
        Constrait[lower_bound(T + 1, T + State + 1, A[i]) - T - 1] |= 1 << (lower_bound(T + 1, T + State + 1, B[i]) - T - 1);
    for(int i = 0; i < All; ++ i)
        for(int j = 0; j < State; ++ j)
            if((i & (1 << j)) && (Constrait[j] & i) != Constrait[j]){
                Avoid[i] = 1;
                break;//break的原因是：这里是判i非法，而只要有一个j令i非法，i就非法
            }
}

void Get_Dp(int R){
    Dp[R][0] = 1;
    for(int i = fir[R]; i != -1; i = edge[i].nxt){//枚举R的每一棵子树
        int v = edge[i].v;
        Get_Dp(v);
        for(int j = All - 1; j >= 0; -- j)  if(! Avoid[j])//枚举状态，要求合法
            for(int k = j; k; k = (k - 1) & j)//将当前合法状态中的1分成两部分，一部分放入v这棵子树中，另一部分放入R的其他子树中
                Dp[R][j] = (Dp[R][j] + 1ll * Dp[R][k ^ j] * Dp[v][k]) % MOD;
				//（注意：这里一定保证前缀（Constrait）合法，不会计算bi和ai被放成兄弟关系的情况，因为非法的划分时Dp[v][k] = 0）
    }
    if(R)
        for(int j = All - 1; j >= 0; -- j)  if(! Avoid[j])
            for(int k = 0; k < State; ++ k)//再次枚举状态，此时处理的是：将R编号标为k，其它的限制在R的子树中（此时前缀关系成立）
                if((j & (1 << k)) && (Constrait[k] & j) == Constrait[k])
                    Dp[R][j] = (Dp[R][j] + Dp[R][j ^ (1 << k)]) % MOD;
}

int main(){
    freopen("similar.in", "r", stdin);
    freopen("similar.out", "w", stdout);
    getint(N);
    for(int i = 0; i < N; ++ i)    scanf("%s", S[i].val), S[i].len = strlen(S[i].val);
    getint(M);
    for(int i = 0; i < M; ++ i)    getint(A[i]);
    for(int i = 0; i < M; ++ i)    getint(B[i]);
    Pre_Work();
    Get_Dp(0);
    Ans = Dp[0][All - 1];
    for(int i = 1; i <= N - State; ++ i)
        Ans = 1ll * Ans * i % MOD;
    printf("%d\n", Ans);
    return 0;
}

给出标程：

（普通C++版）：

#include 

using namespace std;

#define Look(...) fprintf(stderr, __VA_ARGS__)

template 
void Setmax(TAT &a, const TAT &b) 
{
    if (a < b) a = b;
}
template 
void Setmin(TAT &a, const TAT &b)
{
    if (a > b) a = b;
}

typedef long long LL;

#define MAXN  55
#define MOD   1000000007
#define MAXS  ((1 << 16) + 15)

int n;
int fa[MAXN];
struct edge
{
    int to, next;
    edge() {}
    edge(int _t, int _n):to(_t), next(_n) {}
}e[MAXN];
int head[MAXN], et = -1;
int lst[MAXN], lt = 0, N;
int constrait[MAXN];
int f[MAXN][MAXS];
bool ban[MAXS] = {0};

void Addedge(int a, int b)
{
    e[++et] = edge(b, head[a]), head[a] = et;
}

void Dfs(int p)//树形Dp
{
    static int *a, *b;
    memset(f[p], 0, sizeof(f[p]));
    f[p][0] = 1;
    for (int i = head[p]; i != -1; i = e[i].next) {
        Dfs(e[i].to);
        a = f[p];
        b = f[e[i].to];
        for (int j = N - 1; j >= 0; --j) {//枚举子集，合并子树
            if (!ban[j]) {
                for (int k = j; k != 0; k = (k - 1) & j) {
                    a[j] = (a[j] + (LL)a[j ^ k] * b[k]) % MOD;
                }
            }
        }
    }
    if (p != 0) {
        for (int j = N - 1; j >= 0; --j) {//枚举根节点
            for (int k = 0; k < lt; ++k) {
                if (((j >> k) & 1) && (constrait[k] & j) == constrait[k]) {
                    (f[p][j] += f[p][j ^ (1 << k)]) %= MOD;
                }
            }
        }
    }
}

int Solve()
{
    int ans = 0;
    Dfs(0);
    ans = f[0][(1 << lt) - 1];
    for (int i = 1; i <= n - lt; ++i) {//乘上其他位置的阶乘
        (ans = (LL)ans * i % MOD) %= MOD;
    }
    return ans;
}

int Count(vector names, vector info1, vector info2) {
    n = names.size();
    memset(fa, -1, sizeof(fa));
    memset(head, -1, sizeof(head));
    memset(ban, 0, sizeof(ban));
    sort(names.begin(), names.end());
    et = -1;
    for (int i = 0; i < n; ++i) {//处理前缀关系树
        int Max = 0;
        fa[i + 1] = 0;
        for (int j = 0; j < n; ++j) {
            if (i == j || names[i].length() <= names[j].length()) continue;
            bool ok = 1;
            for (int k = 0; k < (int)names[j].length(); ++k) {
                if (names[i][k] != names[j][k]) {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                if (Max < (int)names[j].length()) {
                    Max = (int)names[j].length();
                    fa[i + 1] = j + 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {//建树
        Addedge(fa[i], i);
    }
    lt = 0;
    memset(constrait, 0, sizeof(constrait));
    for (int i = 0; i < (int)info1.size(); ++i) {//离散化受限制位置
        lst[++lt] = info1[i];
        lst[++lt] = info2[i];
    }
    sort(lst + 1, lst + 1 + lt);
    lt = unique(lst + 1, lst + 1 + lt) - lst - 1;
    N = (1 << lt);
    for (int i = 0; i < (int)info1.size(); ++i) {//将每个位置的前缀位置压位
        constrait[lower_bound(lst + 1, lst + 1 + lt, info1[i]) - lst - 1] |= (1 << (lower_bound(lst + 1, lst + 1 + lt, info2[i]) - lst - 1));
    }
    for (int i = 0; i < N; ++i) {//处理不合法状态
        for (int j = 0; j < lt; ++j) {
            if ((i & (1 << j)) && (i & constrait[j]) != constrait[j]) {
                ban[i] = 1;
                break;
            }
        }
    }
    return Solve();
}

int main() {
	vector names;
	vector info1, info2;
	int n, m, t;
	string x;
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> x;
		names.push_back(x);
	} 
	cin >> m;
	for(int i = 0; i < m; i++) {
		cin >> t;
		info1.push_back(t);
	}
	for(int i = 0; i < m; i++) {
		cin >> t;
		info2.push_back(t);
	}
	int Ans = Count(names, info1, info2);
	cout << Ans << '\n';
	return 0;
}

（C++11版）：

#include  

using namespace std;  

#define ui unsigned
#define ll long long

#define pii std::pair
#define mp std::make_pair
#define fi first
#define se second

#define SZ(x) (int)(x).size()
#define pb push_back

templateinline void chkmax(T &x, const T &y) {if(x < y) x = y;}
templateinline void chkmin(T &x, const T &y) {if(x > y) x = y;}

const int N = 50, M = 16;
const int MOD = 1000000007;

int n, m, pn, p[M + 9];
std::vector adj[N + 9];
std::vector vld;
bool ok[1 << M];
std::vector sub[1 << M];
int f[N + 9][1 << M], g[1 << M];

bool prefix(std::string a, std::string b) {// 判断a是否是b的前缀
	return SZ(a) < SZ(b) && b.substr(0, SZ(a)) == a;
}

bool cmp(const std::string &a, const std::string &b) {// 判断a的长度是否 str, vector  a, vector  b) {
	n = SZ(str), m = SZ(a);
	std::sort(str.begin(), str.end(), cmp);// 根据长度排序后，某个字符串的父亲就是最长的是它的前缀的串
	for(int i = 0; i < n; ++i) {
		int fa = n;// 如果没找到，那就连到一个新的空节点
		for(int j = i - 1; j >= 0; --j)
			if(prefix(str[j], str[i])) {// 找到最长的前缀
				fa = j;
				break;
			}
		adj[fa].pb(i);
	}
	// 离散化a和b
	for(auto i : a) p[++pn] = i;
	for(auto i : b) p[++pn] = i;
	std::sort(p + 1, p + pn + 1);
	pn = std::unique(p + 1, p + pn + 1) - p - 1;
	for(int i = 0; i < m; ++i) {
		a[i] = std::lower_bound(p + 1, p + pn + 1, a[i]) - p - 1;
		b[i] = std::lower_bound(p + 1, p + pn + 1, b[i]) - p - 1;
	}
	// 将所有的合法状态提出来，因为如果a是b的前缀，那么a在树中的位置一定是b的位置的祖先
	for(int i = 0; i < (1 << pn); ++i) {
		bool f = true;
		for(int j = 0; j < m; ++j)
			if((i >> a[j] & 1) && !(i >> b[j] & 1)) {// 不可能出现只有a而没有b的情况
				f = false;
				break;
			}
		if(f) vld.pb(i), ok[i] = true;// ok[i]表示i是否合法，vld存储了所有合法的状态
	}
	for(auto s : vld)// 将每个合法状态的合法子状态提出来
		for(int t = s; ; t = (t - 1) & s) {
			if(ok[t] && ok[s - t]) sub[s].pb(t);
			if(!t) break;
		}
	dp(n);
	int ans = f[n][(1 << pn) - 1];
	for(int i = 1; i <= n - pn; ++i) ans = (ll)ans * i % MOD;// 剩下的n - pn个数随意放
	return ans;
}

int main() {
	vector names;
	vector info1, info2;
	int n, m, t;
	string x;
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> x;
		names.push_back(x);
	} 
	cin >> m;
	for(int i = 0; i < m; i++) {
		cin >> t;
		info1.push_back(t);
	}
	for(int i = 0; i < m; i++) {
		cin >> t;
		info2.push_back(t);
	}
	int Ans = Count(names, info1, info2);
	cout << Ans << '\n';
	return 0;
}