首先我们要知道要求什么.显然每次放方块要放一大段不能从中间分开的部分.设\(m=2\)方案为\(f\),\(m=3\)方案为\(g\),\(m=2\)可以放一个竖的,或者两个横的,所以\(f_i=f_{i-1}+f_{i-2}\);\(m=3\),因为只有\(i\)为偶数有值,所以后面的\(i\)其实是\(2i\),然后可以发现要么放三个横的,要么像下面这样放长度为偶数的块

|--|   ------|--|   |----|----   |----|

可以注意到每种长度都有两种方案(长度为\(2\)因为有三个横的所以是三种),所以\(g_i=3g_{i-1}+\sum_{j=2}^{i}2g_{i-j}\),打表可以发现其实是\(g_i=4g_{i-1}-g_{i-2}(g_1=3)\).因为要从某种长度中选\(k\)个,所以要求\((m=2)\sum_{i=l}^r \binom{f_i}{k}\).显然只要考虑\([1,r]\)和\([1,l-1]\)的值

\(k\)较小,我们可以把组合数看成一个\(k+1\)次项的多项式\(\binom{n}{k}=\frac{1}{k!}\prod_{i=0}^{k}(n-i)\),后面记第\(i\)项系数为\(s_i\),那么我们要求的是\[\sum_{i=1}^n \sum_{j=0}^{k} a_j{f_i}^j\]\[ \sum_{j=0}^{k} a_j\sum_{i=1}^n{f_i}^j\]

后面那个东西不大好求,考虑我们已经知道递推式了,可以利用特征方程解出通项公式,可以去学,所以\(f\)的通项公式是自己去网上找,然后稍微改一下,\(g\)的公式是\(g_n=\frac{3-\sqrt{3}}{6}(2+\sqrt{3})^n+\frac{3+\sqrt{3}}{6}(2-\sqrt{3})^n\),后面为了方便,统一记为\(ab^n+cd^n\)

然后继续推式子\[ \sum_{j=0}^{k} a_j\sum_{i=1}^n(ab^i+cd^i)^j\]

二项式定理展开\[ \sum_{j=0}^{k} a_j\sum_{i=1}^n\sum_{l=0}^{j}\binom{j}{l} (ab^i)^l(cd^i)^{j-l}\]\[ \sum_{j=0}^{k} a_j\sum_{l=0}^{j}\binom{j}{l}\sum_{i=1}^n a^lb^ilc^{j-l}d^{i(j-l)}\]\[ \sum_{j=0}^{k} a_j\sum_{l=0}^{j}\binom{j}{l}a^lc^{j-l}\sum_{i=1}^n (b^ld^{j-l})^i\]

后面可以等比数列求和,然后直接做就行了

注意\(3\)和\(5\)在模\(998244353\)意义下没有二次剩余,所以把运算的数记为\(a+b\sqrt{c}\),然后写个类型,定义一下运算就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include