Description:


以上代码为一种字符串hash的写法,给出base和p,试统计长度小于等于n且能使最后hash值为x的字符串(只能包含小写字母)有多少个。

Input:


四个数, \(n\)\(base\)\(p\)\(x\) ( \(1\le n,p,base\le 50000, 0\le x\le p\) )

Output:


一个数表示答案(对998244353取模)

Sample Input:


Sample Output:


题解:


很妙的一道题,可以设状态 \(dp(i, j)\) 表示长度恰好为 \(2^i\) ,Hash值为 \(j\) 的字符串有多少个。

\(f(i, j)\) 表示长度不大于 \(2^i\) ,Hash值为 \(j\) 的字符串有多少个。

可以得到转移:

这个转移是 \(O(n^2)\) 的,注意到可以用NTT优化,时间复杂度 \(O(nlog_2^2 n)\)