Trie树解法

将所有前缀插入trie树，然后根据字符串长度从小到大遍历所有前缀，然后把该字符串的最后一个字符所在结点删除，这样就可以去除所有包含当前前缀的字符串。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 20 * 50;
int tr[N][10],cnt[N], idx;
string arr[52];

int cmp(string a, string b)
{
	return a.size() < b.size();
}
void insert(string s)
{
	int p = 0;
	for(int i = 0; i < s.size(); i++)
	{
		int u = s[i] - '0';
		if(!tr[p][u]) tr[p][u] = ++idx;
		p = tr[p][u];
	}
	cnt[p] = 1;
}

int query(string s)
{
	int p = 0;
	for(int i = 0; i < s.size(); i++)
	{
		int u = s[i] - '0';
		if(!tr[p][u]) return 0;
		p = tr[p][u];
	}
	return cnt[p];
}
void del(string s)
{
	int p = 0, x = s[s.size()-1]-'0';
	for(int i = 0; i < s.size()-1; i++)
	{
		int u = s[i] - '0';
		p = tr[p][u];
	}
	cnt[p] = 0;
    tr[p][x] = 0;
}


int main()
{
	long long n, m;
	cin>>n>>m;
	for(int i = 0; i < m; i++)
	{
		cin>>arr[i];
		insert(arr[i]);
	}
	sort(arr, arr+m, cmp);
	long long res = pow(10, n);
	for(int i = 0; i < m; i++)
	{
		if(query(arr[i]))
		{
			del(arr[i]);
            //cout<<arr[i]<<endl;
            long long temp  = pow(1ll*10, 1ll*n-arr[i].size());
            //cout<<res<<" "<<pow(10, 1ll*n-arr[i].size())<<" ";
			res = res - temp;
            //cout<<res<<endl;
		}
	}
	cout<<res;
}