字典树：
普通字典树用于维护字符串相关信息。

Edu 159 E. Collapsing Strings

c函数实质上就是求a和b的长度之和减去a的最长后缀与b的最长前缀的长度乘2.
那么我们可以把所有的字符先放入trie树，然后在查询的时候进行反转即可。
对于查询有两种办法，对于字符串a而言，我们对其进行反转后，就是在字典树中查询与其匹配的最长公共前缀的长度与个数，长度我们开一个变量进行记录，至于个数，对于长度为len的节点，其最长公共前缀的个数为当前节点数目减去其子节点数目。
再者我们可以对于字符串a，我们删除其第一个字母所花费的代价即为以第一个字母为结尾的字符串个数，以此类推。

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<int, 5> ar;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"int son[N][30],cnt[N],tot=1;
ll n;
ll sum=0;void add(string s)
{int p=1;for(auto x: s){int u=x-'a';if(!son[p][u]) son[p][u]=++tot;p=son[p][u];cnt[p]++;}
}ll query(string s)
{int p=1,len=0;ll res=n*s.size()+sum;for(auto x: s){int u=x-'a';if(!son[p][u]) break;ll pre=cnt[p]-cnt[son[p][u]];res-=len*pre*2;len++;p=son[p][u];}res-=cnt[p]*len*2;return res;
}void solve()
{tot=1,sum=0;cin>>n;vector<string> a(n+5);for(int i=1;i<=n;i++){cin>>a[i];add(a[i]);sum+=a[i].size();}ll ans=0;for(int i=1;i<=n;i++){reverse(a[i].begin(),a[i].end());ans+=query(a[i]);}cout<<ans<<endl;
} int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;// cin>>t;while(t--){solve();}system("pause");return 0;
}

牛客寒假训练营2 C.Tokitsukaze and Min-Max XOR

思路，对于b数组的子序列，我们取其中的最大值和最小值，判断其异或值是否合法，那么对于一个序列而言，我们关心的只有其最大值和最小值，即其他的数都无关紧要。所以先对数组进行排序，然后对于每一个数，我们将其看作最大值，那么对于其前面的数而言，我们看其中有多少最小值是合法的，那么对于当前的位置$i$，其前面确定的合法的最小值位置$j$，那么对于中间的$j-i-1$个数而言，我们共有$2^{j-i-1}$种选择。
再谈及对于最小值的确定，两个数异或的操作，我们自然就可以想到使用01tire树进行维护。
再考虑对于答案的贡献，对于$a_j$,其贡献为$2^{j-i-1}$，我们将这个式子进行变形，即为$\frac{2^j}{2^{i-1}}$,所以我们每个点的价值为$\frac{1}{2^{i-1}}$，我们用逆元进行储存，最后得到总的贡献为$1+2^{i-1}\cdot \sum v_j$。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<int, 3> ar;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
#define endl "\n"int n,k;
int son[30*N][2],cnt[30*N],tot=1;//初始节点赋值为1，若赋值为0，且后续不加判断，就会进入空节点，因为并非所有的节点都存在ll qmi(ll a,ll b,ll c)
{ll res=1;while(b){if(b%2){res=res*a%c;}b>>=1;a=a*a%c;}return res;
}
ll inv(int x)
{return qmi(x,mod-2,mod);
}void add(int x,int v)
{int p=1;for(int i=31;i>=0;i--){int u=x>>i&1;if(!son[p][u]) son[p][u]=++tot;p=son[p][u];cnt[p]=(cnt[p]+v)%mod;}
}ll query(int x)
{int p=1,res=0;for(int i=31;i>=0;i--){int u=x>>i&1;if(k>>i&1){//如果当前位为1，因为u^u=0，所以保证了当前值一定会小于k，所以加上u这一边的贡献，然后走u^1那条路即可res=(res+cnt[son[p][u]])%mod;p=son[p][u^1];}else{//如果当前位为0，因为u^u=0，因为无法确定后续位，那么接着往下走即可。p=son[p][u];}}res=(res+cnt[p])%mod;return res;
}void solve()
{for(int i=1;i<=tot;i++){for(int j=0;j<=1;j++){son[i][j]=0;}}for(int i=1;i<=tot;i++) cnt[i]=0;tot=1;cin>>n>>k;vector<int> a(n+5);for(int i=1;i<=n;i++){cin>>a[i];}sort(a.begin()+1,a.begin()+1+n);ll ans=1;for(int i=2;i<=n;i++){ll res=1;add(a[i-1],inv(qmi(2,i-1,mod)));res=(res+query(a[i])*qmi(2,i-1,mod))%mod;ans=(ans+res)%mod;}cout<<ans<<endl;} int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}