题解：P8643 [蓝桥杯 2016 国 AC] 碱基

· · 题解

思路

易知当 n<m 时，一定无解，特判过掉。
先暴力枚举每个长度为 m 的子串，记录有多少个 DNA 序列中含有这个子串，每个 DNA 序列中含有多少个这个子串，用 set 去重，unordered_map 记录。
再枚举每个去重后的子串，若含有这个子串的 DNA 序列个数 < m，跳过，否则利用乘法原理计算二元组个数，用 ans 求和，在每次求和后取模。
我太蒟了，乘法原理打的多重循环。

代码

#include<bits/stdc++.h>
#define inf 0x7fffffff
#define mod 1000000007
#define ll long long
#define M 500010
#define N 100010
#define quickly ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;;
ll ans,n,m,s;
string ss[7],s1;
ll si;
unordered_map<string,ll> sl,sp[7];
set<string> sset;
int main(){
    quickly;
    cin >>n>>m>>s;
    if(n<m) {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin >>ss[i];
        si=ss[i].size();
        for(int j=0;j<=si-s;j++){
            s1=ss[i].substr(j,s);
            sset.insert(s1);
            if(!sp[i][s1]) sl[s1]++;
            sp[i][s1]++;
        }
    }
    while(!sset.empty()){
        s1=*sset.begin();
        sset.erase(s1);
        if(sl[s1]<m) continue;
        if(m==1){
            for(int i=1;i<=n;i++)
                ans+=sp[i][s1],ans=ans%mod;;
        }else if(m==2){
            for(int i1=1;i1<=n;i1++){
                if(!sp[i1][s1]) continue;
                for(int i2=i1+1;i2<=n;i2++){
                    ans+=sp[i1][s1]*sp[i2][s1],ans=ans%mod;;
                }
            }
        }else if(m==3){
            for(int i1=1;i1<=n;i1++){
                if(!sp[i1][s1]) continue;
                for(int i2=i1+1;i2<=n;i2++){
                    if(!sp[i2][s1]) continue;
                    for(int i3=i2+1;i3<=n;i3++){
                        ans+=sp[i1][s1]*sp[i2][s1]*sp[i3][s1];
                        ans=ans%mod;
                    }
                }
            }
        }else if(m==4){
            for(int i1=1;i1<=n;i1++){
                if(!sp[i1][s1]) continue;
                for(int i2=i1+1;i2<=n;i2++){
                    if(!sp[i2][s1]) continue;
                    for(int i3=i2+1;i3<=n;i3++){
                        if(!sp[i3][s1]) continue;
                        for(int i4=i3+1;i4<=n;i4++){
                            ans+=sp[i1][s1]*sp[i2][s1]*sp[i3][s1]*sp[i4][s1];
                            ans=ans%mod;
                        }
                    }
                }
            }
        }else {
            for(int i1=1;i1<=n;i1++){
                if(!sp[i1][s1]) continue;
                for(int i2=i1+1;i2<=n;i2++){
                    if(!sp[i2][s1]) continue;
                    for(int i3=i2+1;i3<=n;i3++){
                        if(!sp[i3][s1]) continue;
                        for(int i4=i3+1;i4<=n;i4++){
                            if(!sp[i4][s1]) continue;
                            for(int i5=i4+1;i5<=n;i5++){
                                ans+=sp[i1][s1]*sp[i2][s1]*sp[i3][s1]*sp[i4][s1]*sp[i5][s1];
                                ans=ans%mod;
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}