HBC252840[NOIP2018]道路铺设,枚举,前缀和Indivisible Partition题解

为你而来永不停止算法基础篇 2023-11-19 02:17:01 74 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

For example, string abcdeor string ais indivisible, but string aais not indivisible.S , please count the number of different indivisible partitions of

Eva defines a string S S with length n n (indexed from 0 to n-1 n−1 ) is divisible if: the length of S S is greater than 1 1 (i.e. n>1 n>1 ) , and there exists a positive integer kin [1,n) k∈[1,n) satisfying k|n k∣n (i.e. k k is a divisor of n n ) , and for all integer iin [0, n) i∈[0,n) , S_i=S_{i text{mod} k} S i =S i mod k Here S_i S i denotes the character of S S with index i i , for example, let S= S= abcde then S_0= S = a and S_1= S 1 = b. Then, Eva defines a string S S is indivisible if S S is not divisible. For example, string abcde or string a is indivisible, but string aa is not indivisible. Colin defines an indivisible partition of a string S S with length n n as a series of integers {p_1,p_2,dots,p_k} (k ge 2) {p 1 ,p 2 ,…,p k } (k≥2) satisfying: p_1=0, p_k=n p 1 =0, p k =n , and for all integer iin [2, k] i∈[2,k] satisfying p_i>p_{i-1} p i >p i−1 and S[p_{i-1}:p_i-1] S[p i−1 :p i −1] is indivisible. Here S[l:r] S[l:r] denotes the substring of S S with index form l l to r r , for example, let S= S= abcde then S[1:3]= S[1:3]= bcd . Given a string S S , please count the number of different indivisible partitions of S S module 998244353. We consider two indivisible partitions {p_1,p_2,dots,p_{k_1}},{p_1',p_2',dots,p_{k_2}'} {p 1 ,p 2 ,…,p k 1 },{p 1 ′ ,p 2 ′ ,…,p k 2 ′ } are different if k_1not =k_2 k 1  =k 2 , or there exists an integer iin[1, k_1] i∈[1,k 1 ] satisfies p_inot = p_i' p i  =p i ′ . Please note the unusual memory limit.