[HAOI2018]字串覆盖题目描述小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这样一个问题．对于两个长度为n的串A,B,小C每次会给出给出4个参数s,t,l,r.令A从s到t的子串(从1开始标号)为T，令B从l到r的子串为P.然后他会进行下面的操作：如果T的某个子串与P相

\(\text{Solution}\)第二道二项式反演题挺套路的设\(g(i)\)为恰好出现\(S\)次的颜色至少有\(i\)种那么\[g(i)=\binom{m}{i}\binom{n}{is}\frac{(is)!}{(s!)^i}(

思路NTT优化二项式反演。首先考虑到求“正好有\(k\)种颜色出现\(S\)次”的方案数，所以可以考虑转化成求“至少有\(k\)种颜色出现\(S\)次”的方案数。形式化