电子商务网站建设模块,旅游型网站的建设背景,贵州省建设工程造价信息网,中国室内设计艺术千年回眸正题 luoguluoguluogu题目链接:https://www.luogu.org/problemnew/show/CF578D 题目大意
求有多少个字符串TTT使得其和字符串SSS的LCSLCSLCS长度为∣S∣−1|S|-1∣S∣−1 解题思路
首先考虑挖一个空再填一个字母。 这样方案数为n∗n∗mn*n*mn∗n∗m 但是我们考虑aabaabaab这样…正题
luoguluoguluogu题目链接:https://www.luogu.org/problemnew/show/CF578D 题目大意
求有多少个字符串TTT使得其和字符串SSS的LCSLCSLCS长度为∣S∣−1|S|-1∣S∣−1 解题思路
首先考虑挖一个空再填一个字母。 这样方案数为n∗n∗mn*n*mn∗n∗m 但是我们考虑aabaabaab这样的字符无论挖掉哪个aaa都是一样的所有我们将其根据字母相同分为几个块a∣bb∣cc∣d∣ee∣a|bb|cc|d|ee|a∣bb∣cc∣d∣ee∣对于每个快都可以贡献答案n∗n∗mn*n*mn∗n∗m
然后我们再看abababababab有两种方式可以变成aabbaabbaabb也就是隔着相等也会有重复的。而且ababababababababab时有3种重复。也就是隔着相等的越多重复越多而且每次多出来的都是和之前的重复也就是隔着相等有kkk个就有Ck2C_{k}^2Ck2个是重复的减去之后就可以得出答案了。 codecodecode
#includecstdio
#define ll long long
using namespace std;
const ll N110000;
ll n,m,ans,k;
char s[N];
int main()
{scanf(%lld%lld,n,m);scanf(%s,s1);ans1;for(ll i2;in;i)ans(s[i]!s[i-1]);ans*n*m-n;k1;for(ll i2;in;i)if(k1) k(s[i]!s[i-1]);else if(s[i]s[i-2]) k;else{ans-k*(k-1)/2;k(s[i]!s[i-1])1;}ans-k*(k-1)/2;printf(%lld,ans);
}
