题目：

探险家小扣终于来到了万灵之树前，挑战最后的谜题。 已知小扣拥有足够数量的链接节点和 n 颗幻境宝石，gem[i] 表示第 i 颗宝石的数值。现在小扣需要使用这些链接节点和宝石组合成一颗二叉树，其组装规则为：

• 链接节点将作为二叉树中的非叶子节点，且每个链接节点必须拥有 2 个子节点；
• 幻境宝石将作为二叉树中的叶子节点，所有的幻境宝石都必须被使用。

能量首先进入根节点，而后将按如下规则进行移动和记录：

• 若能量首次到达该节点时：
  • 记录数字 1；
  • 若该节点为叶节点，将额外记录该叶节点的数值；
• 若存在未到达的子节点，则选取未到达的一个子节点（优先选取左子节点）进入；
• 若无子节点或所有子节点均到达过，此时记录 9，并回到当前节点的父节点（若存在）。

如果最终记下的数依序连接成一个整数 num，满足 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">num \mod~p=target</annotation></semantics></math>nummod p=target，则视为解开谜题。 请问有多少种二叉树的组装方案，可以使得最终记录下的数字可以解开谜题

注意：

• 两棵结构不同的二叉树，作为不同的组装方案
• 两棵结构相同的二叉树且存在某个相同位置处的宝石编号不同，也作为不同的组装方案
• 可能存在数值相同的两颗宝石

示例 1：

输入：gem = [2,3] p = 100000007 target = 11391299

输出：1

解释： 包含 2 个叶节点的结构只有一种。 假设 B、C 节点的值分别为 3、2，对应 target 为 11391299，如下图所示。 11391299 % 100000007 = 11391299，满足条件; 假设 B、C 节点的值分别为 2、3，对应 target 为 11291399; 11291399 % 100000007 = 11291399，不满足条件； 因此只存在 1 种方案，返回 1[图片上传失败...(image-574b61-1688736784880)]

示例 2：

输入：gem = [3,21,3] p = 7 target = 5

输出：4

解释： 包含 3 个叶节点树结构有两种，列举如下： 满足条件的组合有四种情况： 当结构为下图（1）时：叶子节点的值为 [3,3,21] 或 [3,3,21]，得到的整数为 11139139912199。 当结构为下图（2）时：叶子节点的值为 [21,3,3] 或 [21,3,3]，得到的整数为 11219113913999。[图片上传失败...(image-d29f99-1688736784880)]

提示：

• 1 <= gem.length <= 9
• 0 <= gem[i] <= 10^9
• 1 <= p <= 10^9，保证 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">p</annotation></semantics></math>p 为素数。
• 0 <= target < p
• 存在 2 组 gem.length == 9 的用例

java代码：

#include<bits/stdc++.h>
using namespace std;
namespace Hash{
    typedef unsigned int uint;
    const uint S=16,S1=32-S,M=1996090921;
    #define H(x) ((uint)x*M>>S1)
    struct node{int x,y,t;}h[(1<<S)+105];
    int T=1;
    inline void insert(int x){
        node *p=h+H(x);
        for (;p->t==T;++p)
            if (p->x==x){++p->y; return;}
        p->t=T; p->x=x; p->y=1;
    }
    inline int find(int x){
        for (node *p=h+H(x);p->t==T;++p)
            if (p->x==x)return p->y;
        return 0;
    }
    #undef H
} using namespace Hash;
typedef long long ll;
#define pop __builtin_popcount
const int N=9,M0=205;
int pow10[M0],pinv[M0],l[N],len[1<<N],n,ans,p,r,B;
struct Node{int v1,v2,l;};
int log10(int n){return n<10?1:log10(n/10)+1;}
template<class T> T extend_gcd(T a,T b,T &x,T &y){
    if (!b){x=1;y=0;return a;}
    T res=extend_gcd(b,a%b,y,x); y-=x*(a/b);
    return res;
}
template<class T> T inv(T a,T M){T x,y; extend_gcd(a,M,x,y); return (x%M+M)%M;}
ll fac(int n){ll res=1; while (n)res*=n--; return res;}
ll C(int n,int m){ll res=1; for (int i=1;i<=m;++i)res=res*(n-i+1)/i; return res;}
class Solution {
public:
    vector<int> c[1<<N];
    vector<Node> d[1<<(N+1)];
    template<class F1,class F2,class F3>
    void calc(int t0,F1 f1,F2 f2,F3 f3){
        for (int i=(1<<n)+1;i<(1<<(n+1));++i)d[i].clear();
        for (int i=1<<n;i<(1<<(n+1));++i)if (pop(i)<=t0){
            for (int j=(i-1)&i,_f2;j>>n;j=(j-1)&i)if ((_f2=f2(i,j))||f1(i,j))
                for (auto &t:d[j]){
                    int l1=len[j-(1<<n)]-t.l+2*(j>(1<<n));
                    for (auto &v2:c[i-j]){
                        d[i].push_back({(t.v1+pow10[l1])%p,
                            int(((ll)t.v2*pow10[len[i-j]+1]+(ll)v2*10+9)%p),t.l+len[i-j]+1});
                        if (!_f2)d[i].push_back({int((t.v1+pow10[l1+len[i-j]]+(ll)v2*pow10[l1])%p),
                            int(((ll)t.v2*10+9)%p),t.l+1});
                    }
                }
            int j=(1<<(n+1))-1-i; ++T;
            if (f3(j))continue;
            for (auto &v:c[j])insert(v);
            for (auto &t:d[i])ans+=find((((ll)r-t.v2-(ll)t.v1*pow10[len[j]+t.l])%p+p)*pinv[t.l]%p);
        }
    }
    int treeOfInfiniteSouls(vector<int>& a,int p,int r) {
        n=a.size(); ans=0; B=(n+2)/3; ::p=p; ::r=r;
        if (p==2||p==5)return p==2&&r==1||p==5&&r==4?C((n-1)*2,n-1)/n*fac(n):0;
        pow10[0]=1%p; for (int i=1;i<M0;++i)pow10[i]=(ll)pow10[i-1]*10%p;
        for (int i=0;i<M0;++i)pinv[i]=inv(pow10[i],p);
        for (int i=0;i<n;++i)l[i]=log10(a[i]);
        for (int i=1;i<(1<<n);++i){
            len[i]=(pop(i)*2-1)*2;
            for (int j=0;j<n;++j)if (i&(1<<j))len[i]+=l[j];
        }
        for (int i=0;i<n;++i)c[1<<i].push_back(((ll)a[i]*10+pow10[l[i]+1]+9)%p);
        for (int i=1;i<(1<<n);++i)if (pop(i)<=B*2){  //component below u
            int t=pow10[len[i]-1]+9;
            for (int j=(i-1)&i;j;j=(j-1)&i)
                if (n==9||pop(i)<max((n+1)/2,2)||max(pop(j),pop(i-j))<=min(B,(n-1)/2))
                    for (auto &v1:c[j]){
                        ll t1=(ll)v1*pow10[len[i-j]+1]+t;
                        for (auto &v2:c[i-j])c[i].push_back(((ll)v2*10+t1)%p);
                    }
        }
        d[1<<n].push_back({0,0,0}); //component above u
        auto yes=[](int x,int y=0){return 1;}; auto no=[](int x,int y=0){return 0;};
        if (n==9)
            calc(4,yes,no,[](int j){return pop(j)!=6;}), //remove size 6
            calc(5,[](int i,int j){return j!=(1<<n)||pop(i-j)>=2;}, //remove size 5
                 no,[](int j){return pop(j)!=5;}),
            calc(6,[](int i,int j){return j!=(1<<n)||pop(i-j)==3;}, //remove size 4
                 [](int i,int j){return j==(1<<n)&&pop(i-j)==4;},
                 [](int j){return pop(j)!=4;});
        else calc(n/2+1,yes,[](int i,int j){return n%2==0&&pop(j)==1&&pop(i-j)==n/2;},
                 [](int j){return pop(j)<(n+1)/2||pop(j)>B*2;});
        return ans;
    }
};