KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） Announcement

KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） Announcement

5 hours ago, # | The editorial of G is lacking many details. Can someone provide more details on how we can optimize its DP using matrix exponentiation?

• 5 hours ago, # ^ | ← Rev. 2 →   +11 Suppose we have an empty string and append a character to it times. After appending each character, we must ensure that the current string does not contain any restricted substrings. Suppose is the string after appending characters. Suppose after the th step, we appended character to string such that it becomes . Now we should ensure that does not contain any of the banned substrings. Since is valid till now, we need to look at only the last characters of to check whether it is valid. So we can look at it as a graph with an edge from to . So we start our path from (empty string) and reach . Now we can have many possibilities for , so we cannot store all . Instead, we can just store the last characters of . So, to sum up, you can make a graph of nodes, where each node represents some string which does not contain any banned substring. One node will correspond to an empty string. So you can visualise string as movement(starting from an empty string) from one node to another via directed edge. Since we are only concerned about strings of length less than , . Our answer is a number of walks starting from an empty node with length , which can be easily done using matrix exponentiation. Assume In this case, (notice that actually , but we are only concerned with last characters) (notice that actually , but we are only concerned with last characters) Building graph Link to submission

• 104 minutes ago, # ^ | ← Rev. 3 →   0 Here is the dp const int bit = 6; vector<Mint> dp(1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ if(ok(bit,mask)){ dp[mask]++; } } for(int i = 0; i < n - bit; i++){ vector<Mint> new_dp(1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ for(int k = 0; k < 2; k++){ int new_mask = ((mask << 1) + k) & ((1 << bit) - 1); if(ok(bit,new_mask)){ new_dp[new_mask] += dp[mask]; } } } dp = new_dp; } Where the function ok(size,mask) just checks whether a banned substring occurs in the string mask. Now make the transition matrix from dp to new_dp. matrix<Mint> mat(1 << bit,1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ for(int k = 0; k < 2; k++){ int nmask = ((mask << 1) + k) & ((1 << bit) - 1); if(ok(bit,nmask)){ mat[mask][nmask] = 1; } } } Notice that new_dp = mat * dp. Your final answer is now power(mat,(n-bit)) * dp. You can calculate final dp in instead of using binary exponentiation. Here is my submission https://atcoder.jp/contests/abc305/submissions/42175122.