首页 > 其他分享 >CF163A Substring and Subsequence 题解

CF163A Substring and Subsequence 题解

时间:2024-03-05 19:00:49浏览次数:35  
标签:ch limits 题解 sum Substring il auto CF163A define

分析

考虑 DP。

定义状态函数 $f_{i,j}$ 表示在 $s[1\dots i]$ 中选一个子串 $a$,在 $t[1 \dots j]$ 中选一个子序列 $b$,且 $s_i,t_j$ 必选时 $a=b$ 的方案数。则有两种情况:

  1. $s_i \ne t_j$。此时 $a$ 和 $b$ 是不可能相同的了,所以 $f_{i,j}=0$。
  2. $s_i = t_j$。在只选 $s_i,t_j$ 时有 $1$ 种方案,而不止选 $s_i,t_j$ 时根据枚举前一个字符选的位置,有 $\sum\limits_{k=1}^{j-1} f_{i-1,k}$ 种方案。所以 $f_{i,j}=1+\sum\limits_{k=1}^{j-1} f_{i-1,k}$。

整合一下有转移方程:$f_{i,j}=[s_i=t_j]\times(\sum\limits_{k=1}^{j-1}f_{i-1,k}+1)$。定义 $s_{i,j}=\sum\limits_{k=1}^{j} f_{i,k}$,则有:$f_{i,j}=[s_i=t_j]\times(s_{i,j-1}+1)$。这就是个前缀和优化,在更新完 $f_{i,j}$ 只后直接更新 $s_{i,j}$ 即可。

答案就是 $\sum\limits_{i=1}{|s|}\sum\limits_{j=1}f_{i,j}$。复杂度 $O(n^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	il auto max(auto a,auto b){return (a>b?a:b);}
	il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=5005,p=1e9+7;
int f[N][N],s[N][N];
char a[N],b[N];
int n,m;

il void solve(){
	scanf("%s",a+1),n=strlen(a+1);
	scanf("%s",b+1),m=strlen(b+1);
	for(re int i=1;i<=n;++i)
	for(re int j=1;j<=m;++j){
		f[i][j]=(long long)((a[i]==b[j])*(s[i-1][j-1]+1))%p;
		s[i][j]=(long long)(s[i][j-1]+f[i][j])%p;
	}
	long long ans=0;
	for(re int i=1;i<=n;++i) ans=(ans+s[i][m])%p;
	printf("%lld\n",ans);
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int t=1;while(t--)
	solve();
	return 0;
}

标签:ch,limits,题解,sum,Substring,il,auto,CF163A,define
From: https://www.cnblogs.com/harmisyz/p/18054664

相关文章

  • CF101B Buses 题解
    分析考虑DP。由于$n$很大,而$m$可以接受,考虑根据公交车定义状态函数。很容易想到一种状态函数:$f_i$表示做第$i$辆公交车到$t_i$的方案数。根据题意,就有转移方程:$f_i=\sumf_j[s_i\let_j\let_i-1]+k$,$k$在$s_i=0$时为$1$,其余为$0$。然后这题就会了。求和部分......
  • AT_abc263_f [ABC263F] Tournament 题解
    分析一眼DP。定义状态函数$f_{i,j}$表示在第$i$此比赛中,获胜者为$j$时的最大奖学金。把比赛过程看成一棵倒着的满二叉树,就能发现:第$i$场比赛只会是其左儿子为根的子树中叶子节点的某一个与其右儿子为根的子树中叶子节点的某一个进行比赛。然后就可以得到转移方程:$f_{i,......
  • P10149 [Ynoi1999] XM66F 题解
    分析考虑莫队。对于$a_i=k(l\lei\ler)$的下标集合$S_k$,当其加入一个新的下标$x$时,这个新下标对答案的贡献分两种情况。第一种,$x$最小。相邻从下标的间隔中产生的贡献是$\sum(|S_k|-i+1)\times(ans_{S_{k,i+1}}-ans_{S_{k,i}})$。画个图可以理解一下:第二中,$x$最......
  • AT_abc343_G [ABC343G] Compress Strings 题解
    分析水题,评分能有$2100$可能是因为很多人卡E了。我说真的,E好难啊。$n$只有$20$,考虑从状压的角度入手。定义状态函数$f_{s,i}$表示当某个字符串$T$包含了所有$s$的二进制中为$1$的下标$S_j$且$T$末尾包含的子串为$S_i$时$T$的最小长度。那很显然的就有转......
  • 题解:卡农(组合计数+DP)
    题面题目链接简化一下,有\(3\)个限制:不能是空集。每个元素出现的次数必须为偶数。不能出现两个相同的集。思路首先不用状压,但是需要\(DP\),因为\(n\)范围过大用状压内存放不下,不然本来状压很好用的。考虑数学方法\(+DP\)。限制\(1\)因为不能有空集,所以可选......
  • tomcat8.5+ windows中html页面及控制台中文乱码问题解决办法
    tomcat8.5+windows中html页面及控制台中文乱码问题解决办法————————————————版权声明:本文为博主原创文章,遵循CC4.0BY-SA版权协议,转载请附上原文出处链接和本声明。原文链接:https://blog.csdn.net/onemy/article/details/106215384 https://blog.csdn.......
  • 题解 P10220【[省选联考 2024] 迷宫守卫】
    \(\text{Link}\)葬送了我2024省选的一题。题意有一颗深度为\(n+1\)的完全二叉树,其叶子上依次标有一个长为\(2^n\)排列\(a\),非叶结点有选择代价\(b_i\)。Alice、Bob两人进行游戏。Alice可以选择一些选择代价和不超过\(m\)的非叶结点,此后Bob会从根开始深度优先搜索......
  • 2024-selenium-问题一:java.io.IOException: Invalid Status code=403 text=Forbidden
    问题截图:  问题分析: 参考网址:https://blog.csdn.net/weixin_46739493/article/details/134163739问题解决:1、chrome版本为:版本114.0.5735.199(正式版本);driver的版本为:114.0.5735.90; java-seleium版本为:4.0.0-rc-21<dependency>2<groupId>org.......
  • [省选联考 2024] 题解
    D1T1P10217季风题意有点抽象,大概就是要求我们对两个有若干次重复的序列进行操作,每次可以将这两个序列都向上或向下调整一个值,但是调整的绝对值的总和有限制,问能否最终将总和调整至固定值。由于\(m\)不一定是\(n\)的倍数,因此序列在重复若干次之后可能会遗留一些散块,这是不......
  • P10217 [省选联考 2024] 季风 题解
    [省选联考2024]季风Description给定\(n,k,x,y\)和\(2n\)个整数\(x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}\)。找到最小的非负整数\(m\),使得存在\(2m\)个实数\(x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'\)满足以下条件,或报告不存在这样的\(m\):\(\s......