https://www.luogu.org/problem/show?pid=1666 首先空集合也是答案，所以样例是对的； 那么我们思考； 假如两个串ab； a< b 如果这个时候a不是b的前缀； 那么所有字典序小于a的并且不是a的前缀的字符串均不是b的前缀； 所以我们先对串排序，然后直接dp f[i][j]表示1~j号串里取i个（j号必须取）的所哟方案数； f[0][0]=0；
#include<bits/stdc++.h> #define Ll long long using namespace std; const Ll N=55; string s[N]; Ll f[N][N]; Ll n,ans; bool can(string a,string b){ Ll l=min(a.length(),b.length()); for(Ll i=0;i<l;i++)if(a[i]!=b[i])return 1; return 0; } int main() { scanf("%lld",&n); for(Ll i=1;i<=n;i++)cin>>s[i]; sort(s+1,s+n+1); f[0][0]=1; for(Ll i=1;i<=n;i++) for(Ll j=1;j<=n;j++) for(Ll k=0;k<j;k++) if(!k||can(s[k],s[j])) f[i][j]+=f[i-1][k]; for(Ll i=0;i<=n;i++) for(Ll j=0;j<=n;j++) ans+=f[i][j]; printf("%lld",ans); }