CSES - Empty String
Author: Dong Liu
Editorial
Let represent the number of ways to empty the substring .
To calculate , we loop through indices between and where .
Then, if we choose to remove and , we must remove the range first (for and to be adjacent). Here, the number of ways to remove the range is .
We also need to remove for the whole substring to be removed (the number of ways to do this is ).
Since we can remove the substring and in any order, we also multiply this by (notice that we divide the sizes by two because we remove the letters in pairs).
Thus our transition would be
such that .
Implementation
Time Complexity:
C++
#include <bits/stdc++.h>using namespace std;#define N 500#define MOD 1000000007int add(int a, int b) {if ((a += b) >= MOD) a -= MOD;return a;}
Python
N = 500MOD = 10**9 + 7def add(a: int, b: int) -> int:return (a + b) % MODdef mul(a: int, b: int) -> int:return (a * b) % MOD
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!