专栏文章

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

zzhaocs123456
P8643题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miozgke4
此快照首次捕获于
2025/12/03 03:40
3 个月前
此快照最后确认于
2025/12/03 03:40
3 个月前
查看原文

思路

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

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...