A40849. 碱基
填空题
困难
知识点
题目描述
碱基
题目描述
生物学家正在对n个物种进行研究。
其中第i个物种的DNA序列为s[i]，其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。
生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组( i1,p1,i2,p2....im,pm )表示，
满足:1<=i1<i2<....<im<=n;
且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=....=s[im][pm+q]。
现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。
输入格式
输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，意义如题目所述。
接下来n行，每行一个字符串表示一种生物的DNA序列。
DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，不同的生物的DNA序列长度可能不同。
输出格式
输出一个整数，表示关注的元组个数。
答案可能很大，你需要输出答案除以 1000000007 的余数。
样例输入
3 2 2
ATC
TCG
ACG
样例输出
2
样例输入
4 3 3
AAA
AAAA
AAA
AAA
样例输出
7
参考答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10;
const ll MOD = 1000000007;
int n, m, k;
ll ans, res;
string s;
vector<int> v; // 代码中讲
map<string, int> cnt[N], vis; // cnt[i][str]表示第i个字符串中长度为k的子串str的个数 vis[str]表示str是否为全部字符串中某个字符串的长度为k的子串
void dfs(int x, int num, ll sum) { // x表示v中的索引，num表示已选个数，sum表示已选数的乘积
if(num == m) {res = (res + sum)%MOD; return ;}
if(x == v.size()) return ;
dfs(x+1, num, sum);
dfs(x+1, num+1, sum*v[x]%MOD);
}
int main()
{
cin>>n>>m>>k;
for(int i = 1;i <= n;i ++) {
cin>>s;
int nn = s.size();
for(int j = 0;j < nn-k+1;j ++) {
string str = s.substr(j, k); // 获取全部长度为k的子串
cnt[i][str] ++; // 第i个字符串的子串str个数+1
vis[str] = 1; // 标记存在子串str
}
}
for(map<string,int>::iterator it = vis.begin();it != vis.end();it ++) { // 枚举子串
v.clear(); // !!!
for(int i = 1;i <= n;i ++) {
string tmp = it->first;
int num = cnt[i][tmp]; // 第i个字符串中子串tmp的个数
if(num) v.push_back(num); // 第i个字符串中子串tmp的个数不为0，则加入数组中
}
if(v.size() >= m) {
res = 0LL; // res用于暂存每种组合的乘积
dfs(0, 0, 1LL);
ans = (ans + res) % MOD;
}
}
cout << ans;
return 0;
}
上一题
下一题