subsequence 1
题意
给出两个数字串s,t，求s的子序列中在数值上大于t串的数量
分析
数字大于另一个数字，要么位数多，要么位数相同，字典序大，位数多可以很方便地用组合数学来解决，所以只剩下了位数相同的情况，如何实现呢，我们考虑定义状态dp[i][j][0/1]分别表示s串前i个字符中长度为j的串前面的字符等于t串相应长度的前缀的数量，1则表示大于的数量 ，然后分三种情况转移即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P=998244353;
const int maxn=3005;
const int M=3005;
char s[maxn],t[maxn];
ll dp[maxn][maxn][2];
ll F[maxn],Finv[maxn],inv[maxn];
ll pw(ll bs,ll x){
ll ans=1;
while(x){
if(x&1)ans=ans*(bs%P)%P;
bs=bs*(bs%P)%P;
x>>=1;
}
return ans;
}
void init(){
F[1]=Finv[1]=inv[1]=Finv[0]=inv[0]=1;
for(int i=2;i<M;i++)inv[i]=inv[P%i]*(P-P/i)%P;
for(int i=2;i<M;i++){
Finv[i]=Finv[i-1]*inv[i]%P;
F[i]=F[i-1]*i%P;
}
}
ll C(int n,int m){
if(m<0||n<m)return 0;
if(m==0||n==m)return 1;
return F[n]%P*(Finv[n-m]%P)%P*Finv[m]%P;
}
int main(){
int n,m;
int T;
scanf("%d",&T);
init();
while(T--){
scanf("%d%d",&n,&m);
scanf("%s%s",s+1,t+1);
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<2;k++)dp[i][j][k]=0;
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
dp[i][1][0]=dp[i-1][1][0];
dp[i][1][1]=dp[i-1][1][1];
if(s[i]==t[1]&&t[1]!='0'){dp[i][1][0]++;dp[i][1][0]%=P;}
if(s[i]>t[1]){dp[i][1][1]++;dp[i][1][1]%=P;}
for(int j=2;j<=max(m,i);j++){
if(s[i]<t[j]){
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j-1][1])%P;
}
else if(s[i]==t[j]){
dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j-1][0])%P;
dp[i][j][1]=(dp[i-1][j-1][1]+dp[i-1][j][1])%P;
}
else if(s[i]>t[j]){
dp[i][j][1]=(dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j][1])%P;
dp[i][j][0]=dp[i-1][j][0];
}
}
}
long long sum=dp[n][m][1];
/*for(int i=m;i<=n;i++){
sum=dp[i][m][1];sum%=P;
}*/
for(int i=1;i<=n-m;i++){
if(s[i]=='0')continue;
for(int j=m;j<=n-i;j++){
sum+=C(n-i,j);sum%=P;
}
}
printf("%lld\n",sum);
//cout<<sum<<endl;
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<"1 :"<<dp[i][j][1]<<" 0: "<<dp[i][j][0]<<" ||";
}
cout<<endl;
}*/
}
return 0;
}