2018 计蒜之道 复赛 G

2019-04-14 20:23发布

站内文章 / 模拟电子
16279 0 1710
题目链接题面：贝壳找房举办了一场计数比赛，比赛题目如下。给一个字符串 ss 和字符串 tt，求出 ss 的所有去重全排列中 tt 出现的次数。比如aab的去重全排列为aab、aba、baa。注意aaaa算出现两次aaa。你的老大希望你帮他写一个程序作弊。思路：先在s串中删除t串得到m串，计算m串的去重全排列数量，然后在所有m串所有位置中插入t串，就能得到结果代码：#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define pi acos(-1) #define mod (1000000007) #define fin(num,n) for(int aaa=0;aaa>num[aaa++]) #define fout(num,n) for(int aaa=0;aaa>num[aaa][bbb++]) #define ffout(num,n,m) for(int aaa=0;aaa>= 1; } return ans; } int main() { ios::sync_with_stdio(false); cout << fixed << setprecision(0); init(); while(cin>>T) while (T--) { cin >> s >> t; int mp[30] = { 0 }, sum = 0; for (int a = 0; a < s.size(); a++) mp[s[a] - 'a']++; for (int a = 0; a < t.size(); a++) mp[t[a] - 'a']--; for (int a = 0; a < 30; a++) if (mp[a] < 0) { sum = -1; break; } else sum += mp[a]; if (sum == -1) cout << 0 << endl; else if (sum == 0) cout << 1 << endl; else { ll ans = jie[sum]; for (int a = 0; a < 29; a++) if(mp[a]>1) ans *= suan(jie[mp[a]], mod - 2), ans %= mod; ans *= sum+1; ans %= mod; cout << ans << endl; } } return 0; }

热门文章