链接：https://ac.nowcoder.com/acm/contest/885/G
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
You are given two strings s and t composed by digits (characters '0' ∼\sim∼ '9'). The length of s is n and the length of t is m. The first character of both s and t aren't '0'.
Please calculate the number of valid subsequences of s that are larger than t if viewed as positive integers. A subsequence is valid if and only if its first character is not '0'.
Two subsequences are different if they are composed of different locations in the original string. For example, string "1223" has 2 different subsequences "23".
Because the answer may be huge, please output the answer modulo 998244353.
输入描述:
The first line contains one integer T, indicating that there are T tests.
Each test consists of 3 lines.
The first line of each test contains two integers n and m, denoting the length of strings s and t.
The second line of each test contains the string s.
The third line of each test contains the string t.
* 1≤m≤n≤30001 \le m \le n \le 30001≤m≤n≤3000.
* sum of n in all tests ≤3000\le 3000≤3000.
* the first character of both s and t aren't '0'.
输出描述:
For each test, output one integer in a line representing the answer modulo 998244353. 示例1
输入
3
4 2
1234
13
4 2
1034
13
4 1
1111
2 输出
9
6
11 说明
For the last test, there are 6 subsequences "11", 4 subsequcnes "111" and 1 subsequence "1111" that are valid, so the answer is 11. 题目大意:给一个字符串t,一个字符串s,找出s中有多少个子串大于字符串t.
题目思路:
首先长度大于m的绝对可以,所以我们先用组合数算出来.随后等于m的我们需要判断
第一次见这种dp(学艺不精,推了好久才推出来),我们用 f(i,j)表示当前s长度为i的后缀有多少个长度为j的子串并且大于长度为t长度为j的后缀.首先还是搞清楚为什么可以DP:
首先,关于每一个长度为s的后缀,我们判断它符不符合题意,可以分两种情况:
第一:他作为当前子串的开头 ,现在又需要分三种情况.
因为m的后缀是固定的:m当前长度为j的后缀首位是 m[m-j+1],令x=m[m-j+1]
1.如果num[n-i+1]>x 则他可以进行与之前长度为i-1里的j-1个数任意组合,答案 C(i-1,j-1)
2.如果num[n-i+1]==x 则他可以和 i-1,j-1组成满足要求的答案 :f(i-1,j-1)
3.如果num[n-i+1]==x 则他什么也不可以,只能继承上一个状态.
第二:他不作为当前子串的开头,那么现在符合题意的就是 上一个前缀符合题意的个数
所以答案就是 第一种状态(分这三种小状态)+第二种状态(分类相加)
具体看一下,状态转移方程带注释:
f(i,j)=
{
f(i,j)=0 ---------i<j
f(i,j)=f(i-1,j)+1 --------num[n+1-i]>num[m]&&j==1//j==1的时候需要特判一下,因为如果 目标求 23 ,假设现在后缀以2为开头 2 4是可以的,所以相等是可以的,但如果后缀长度是1,只能让他保证大于.
f(i,j)=f(i-1,j) --------num[n+1-i]<=num[m]&&j==1//此时没有解
f(i,j)=f(i-1,j) ---------num[n+1-i]<num[m+1-j]
f(i,j)=f(i-1,j)+f(i-1,j-1) ---------num[n+1-i]==num[m+1-j]
f(i,j)=f(i-1,j)+C(i-1,j-1) ---------num[n+1-i]>num[m+1-j]
}
最后还需要注意一点就是 num[i]=0时候直接继承就好了,关于空间复杂度问题,如果想要优化的话,可以看到这个DP是只与上一层的状态有关的所以,可以加一个滚动数组来优化
附上AC代码(我没优化),记得最后相加还要取余!第一次wa在了没取余:
/*
代码长度：1650 运行时间： 109 ms 占用内存：117532K
*/
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e6+8;
const double eps=1e-10;
const ll mod=998244353;
ll n,m,K;
ll dp[3005][3005];
ll ta[3005][3005];
ll s[3005],t[3005];
void build()
{
for(int i=1;i<3005;i++) ta[i][0]=1;
ta[1][1]=1;
for(int i=2;i<3005;i++)
for(int k=1;k<=i;k++)
ta[i][k]=(ta[i-1][k-1]+ta[i-1][k])%mod;
}
int main()
{
build();
int T;
scanf("%d",&T);
while(T--)
{
ll sum=0;
scanf("%lld%lld",&n,&m);
for(int k=0;k<=m;k++) dp[0][k]=0;
for(int i=1;i<=n;i++) scanf("%1lld",&s[i]);
for(int i=1;i<=m;i++) scanf("%1lld",&t[i]);
for(int i=1;i<=n;i++)
{
if(s[i]!=0)
{
ll temp=n-i;
for(int k=m;k<=temp;k++)
{
sum+=ta[temp][k];
sum%=mod;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i]==0) dp[i][j]=dp[i-1][j];
if(i<j) dp[i][j]=0;
else if(j==1)
{
if(s[n+1-i]>t[m]) dp[i][j]=(dp[i-1][j]+1)%mod;
else dp[i][j]=dp[i-1][j];
}
else if(s[n+1-i]<t[m+1-j]) dp[i][j]=dp[i-1][j];
else if(s[n+1-i]==t[m+1-j]) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
else if(s[n+1-i]>t[m+1-j]) dp[i][j]=(dp[i-1][j]+ta[i-1][j-1])%mod;
}
}
printf("%lld\n",(sum+dp[n][m])%mod);
}
return 0;
}
京公网安备 11010502036488号