题面大意:
- 给定2个字符串,问有多少个子字符串S, 是大于t的
思路
- 数据范围很小, 因此考虑n^2做法
- 分2步, 位数s>位数t 的时候
- 然后 位数相等的时候
- 利用DP ,处理, 分别就是枚举 前 k个数和s相同,然后k+1个数比t大就可以.
- 具体思路自己想想,和那个比较像
const int MOD = 998244353; ll dp[3001][3001]; ll c[3001][3001]; void init() { c[0][0] = 1; for(int i = 1; i <= 3000 ; ++ i) { c[i][0] = c[i][i] = 1; for(int j = 1 ; j < i ; ++ j) { c[i][j] = c[i-1][j] + c[i-1][j-1]; c[i][j] %= MOD; } } } int main() { init(); int T; cin >> T; while(T--) { char s1[3001] , s2[3001]; int len1 , len2; ll sum = 0; scanf("%d%d",&len1,&len2); scanf("%s%s",s1+1,s2+1); dp[0][0] = 1; for(int i = 1 ; i <= len1 ; ++ i) { dp[i][0] = 1; for(int j = 1 ; j <= min(len2,i) ; ++ j) { dp[i][j] = dp[i-1][j]; if( s1[i] == s2[j] ) dp[i][j] += dp[i-1][j-1], dp[i][j] %= MOD; if( s1[i] > s2[j]) sum += ( dp[i-1][j-1] * c[len1-i][len2-j] ) % MOD; } } for(int i = 1 ; i <= len1; ++ i) if( s1[i] != '0') { for(int k = len2 ; k <= len1 - i; ++ k) sum += c[len1-i][k], sum %= MOD; } printf("%lld\n",sum); } }