随风飘

是一个组合数学问题,朴素的对于每个都不取k,那就是两个for的事.但是对于取k,我们应该如何分析呢?
总的是n,我们拿走k个.在拿走的过程中,我们考虑始终保留两个特殊的,假设说我不存在取的过程,那么这两个产生的贡献必定是一次lcp.但是我们考虑拿走,这个它会多几次呢?其实也挺显然的,C(n-2,k)考虑保留这两个,然后再取走k就没了.那么就变成了如何快速的求两个的lcp,可以直接存下每个的哈希值然后二分..但是呢?这题可以直接暴力比较emm..很水吧,优化数据结构就交给徐鹏大佬了???反正我不是学数据结构的..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3000000,M=4005;
const int mod=1e9+7;
string s[M];
char ss[N];

ll fact[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline ll C(ll n,ll m)
{
    ll res=fact[n];
    return res*qp(fact[m],mod-2)%mod*qp(fact[n-m],mod-2)%mod;
}

void init()
{
    fact[1]=1;fact[0]=1;
    for(int i=2;i<=M-5;i++)
    {
        fact[i]=i*fact[i-1]%mod;
    }
}

int main()
{
    init();
    ll n,q;
    scanf("%lld%lld",&n,&q);
    for(int i=0;i<n;i++)
    {
        scanf("%s",ss);
        s[i]=ss;
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int k;
            for(k=0;k<min(s[i].size(),s[j].size());k++)
            {
                if(s[i][k]!=s[j][k]) break;
            }
            ans+=k;
        }
    }
    while(q--)
    {
        ll x;
        scanf("%lld",&x);
        printf("%lld\n",C(n-2,x)*ans%mod);
    }
    return 0;
}