A. 小星星
考虑一个大家都会的暴力 dp：设 (f_{v,i,S}) 表示确定好了 (v) 的子树内的点映射到集合 (S) 上，并且 (v) 对应 (i) 的方案数。合并子树的时候要保证 (S1) 和 (S2) 不交，然后根据图是否有边来判断。
复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 (S) 然后跑上面去掉第三维后的 dp ，设得到的方案数为 (f(S))，那么 (f(S)) 表示 (n) 个点，映射到的点的集合 (subseteq S) 的方案数，而我们要求 (g(S)) 表示 (n) 个点，映射到的点的集合 (=S) 的个数。
那么我们有
[f(S) = sum_{T subseteq S} g(T)
]
根据子集容斥，可以得到
[g(S) = sum_{T subseteq S} (-1)^{|S|-|T|}f(T)
]
所以我们只需要枚举子集，(O(2^n n^3)) 才能过。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 17 + 1;
int n,m;
int G[MAXN][MAXN];
std::vector<int> T[MAXN];
LL f[MAXN][MAXN];
std::vector<int> lim;
inline void merge(int x,int y){
for(auto i:lim){
LL s = 0;
for(auto j:lim){
if(!f[y][j]) continue;
if(!G[i+1][j+1]) continue;
s += f[y][j];
}
f[x][i] *= s;
}
}
inline void dfs(int v,int fa=0){
for(auto i:lim) f[v][i] = 1;
for(auto x:T[v]){
if(x == fa) continue;
dfs(x,v);
merge(v,x);
}
}
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,m){
int u,v;scanf("%d%d",&u,&v);
G[u][v] = G[v][u] = 1;
}
FOR(i,1,n-1){
int u,v;scanf("%d%d",&u,&v);
T[u].pb(v);T[v].pb(u);
}
LL res = 0;
FOR(S,1,(1<<n)-1){
if(__builtin_popcount(S) == 1) continue;
LL gx = 0;lim.clear();CLR(f,0);
FOR(i,0,n-1) if((S>>i)&1) lim.pb(i);
dfs(1);
FOR(i,0,n-1) if((S>>i)&1) gx += f[1][i];
if((n-__builtin_popcount(S))&1) gx = -gx;
res += gx;
}
printf("%lld
",res);
return 0;
}
B. 魔法小程序
首先可以把 (a) 的长度缩短的 (O(log n)) 级别。注意需要把 (1) 去掉。
然后我们看一下给出的程序在做什么：相当于用那个递归程序写成若干个字符串后，求高维前缀和。
那么我们考虑高维前缀和如何做：在第一层的时候我们设 (x=a_0)，按照 (x) 分组，每组内都是第一位递增的，所以每组内部都 (b_i += b_{i-1})，然后我们到下一层，那么原来的每 (x) 组在下一层中的最低位都是一样的，设 (y=a_0a_1)，按照 (y) 分组，也是在每一组内 (b_i += b_{i-x})，剩下的也是类似做。。
那么高维前缀和的逆就是倒着做，每次倒着减掉就行了。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e6 + 5;
int a[MAXN],n,b[MAXN],m;
std::vector<int> basis;
int main(){
scanf("%d",&n);
FOR(i,0,n-1) scanf("%d",a+i);
scanf("%d",&m);
FOR(i,0,m-1) scanf("%d",b+i);
basis.pb(1);
FOR(i,0,n-1){
if(a[i] == 1) continue;
if(basis.back()*a[i] > m-1) break;
basis.pb(basis.back()*a[i]);
}
basis.pb(m);
ROF(cc,(int)basis.size()-1,1){
for(int i = 0;i < m;i += basis[cc]){
int j = std::min(m-1,i+basis[cc]-1);
while(j >= i+basis[cc-1]) b[j] -= b[j-basis[cc-1]],--j;
}
}
printf("%d
",n);
FOR(i,0,n-1) printf("%d%c",a[i],"
"[i==n-1]);
printf("%d
",m);
FOR(i,0,m-1) printf("%d%c",b[i],"
"[i==m-1]);
return 0;
}
C. 组合数问题
卢卡斯定理拆成 (p) 进制下的问题，我们将 (n,m) 在 (p) 进制下分解，如果 (mod p=0) 那么就说明存在一位 (a_i < b_i)。
所以可以设计数位dp：设 (f_{i,0/1,0/1,0/1,0/1}) 表示考虑前 (i) 位，是否已经有 (a_i<b_i)，(j) 是否卡 (i) 上界，(i) 是否卡 (n) 上界，(j) 是否卡 (m) 上界，枚举转移即可。复杂度 (O(qlog_p^3))
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 60+5;
const int ha = 1e9 + 7;
int a[MAXN],b[MAXN],len;
inline void add(int &x,int y){
x += y;if(x >= ha) x -= ha;
}
/*
C(i,j)
f[考虑到哪一位][是否有i<j][j是否卡i上界][i是否卡n上界][j是否卡m上界]
*/
int f[MAXN][2][2][2][2],k;
inline int dp(int i,int ok,int b1,int b2,int b3){
// DEBUG(i);
if(i > len) return ok;
if(f[i][ok][b1][b2][b3] != -1) return f[i][ok][b1][b2][b3];
int &res = f[i][ok][b1][b2][b3];res = 0;
int lim1 = b2?a[i]:(k-1);
FOR(x,0,lim1){
int lim2 = std::min(b1?x:(k-1),b3?b[i]:(k-1));
FOR(y,0,lim2){
add(res,dp(i+1,ok|(x<y),b1&(y==x),b2&(x==a[i]),b3&(y==b[i])));
}
}
return res;
}
int main(){
int T;scanf("%d%d",&T,&k);
while(T--){
LL n,m;scanf("%lld%lld",&n,&m);
m = std::min(n,m);CLR(a,0);CLR(b,0);
CLR(f,-1);
int lena = 0,lenb = 0;
while(n) a[++lena] = n%k,n /= k;
while(m) b[++lenb] = m%k,m /= k;
len = std::max(lena,lenb);
std::reverse(a+1,a+len+1);std::reverse(b+1,b+len+1);
printf("%d
",dp(1,0,1,1,1));
}
return 0;
}