正题

首先因为撞题的原因，而导致比赛，给大家带来了不少的困扰，在此说声对不起。

出题人在构造的时候至少自己想了三小时，可能是由于先想算法再想题的原因，导致题目容易翻车，不管你对出题人抱有怎样的不满，不管你对这次的比赛有多么困惑，都是出题人的错，请大家继续相信的比赛。出题人水平不够，如果水平没有提高的话，以后也不太可能出题了，这次出比赛的确挺打击我的自信心的。评论区轻喷。

下面就是正经的题解了。
​

T1

首先使用kmp算法来找出每一个匹配的位置。为了不给不细心的人一血，改了模数。
考虑使用表示前缀中，提取组合包括i的一个后缀的方案数。
令。
考虑当前位置为，我们枚举前面的断点位置，表示这次选择是，这个区间必须要包括最后一次匹配的位置，如果当前没有匹配过，显然。
那么就有，即，其中表示上一次匹配的开头位置。

#include<bits/stdc++.h>
using namespace std;

const int mod=99824353;
const int N=1000010;
char s[N],t[N];
int nex[N],n,m,f[N],sum[N],ss[N];

int main(){
    scanf("%s",s+1);
    scanf("%s",t+1);
    n=strlen(s+1);m=strlen(t+1);
    nex[0]=-1;
    for(int i=1;i<=m;i++){
        int now=nex[i-1];
        while(now!=-1 && t[now+1]!=t[i]) now=nex[now];
        nex[i]=now+1;
    }
    int l=1,r=1;f[0]=sum[0]=ss[0]=1;
    int las=-1;
    while(l<=n){
        r--;while(r!=-1 && t[r+1]!=s[l]) r=nex[r];
        if(r==m-1) las=l-m;
        if(las!=-1) f[l]=ss[las];
        sum[l]=(sum[l-1]+f[l])%mod;
        ss[l]=(ss[l-1]+sum[l])%mod;
        r+=2;l++;
    }
    printf("%d\n",sum[n]);
}

T2

挺套路的，但是实在没有见过原题，就出了出来，再次抱歉。

考虑对于这些数字串建出自动机，然后将图建出来。

我们先在加字符串的时候，将每一个字符串的末尾标记一下，然后建图的时候下传一下标记，即指针若被标记了，那么当前就被标记。

现在我们在整张图上跑数位就可以了，设表示最后剩个位置没填，现在在图上走到的位置的方案数（无前缀0和位的限制）。

时间复杂度就为，可以通过此题。

T3

考虑设表示给的星星数，特别的表示给的星星数，注意这里的 是有符号的。

发现，如果确定了的值，其他也就确定了。

令为平均数，关系表示为，即。

推理，有，即

即有

我们将其通通减掉，得到一个序列。

需要令最小。

考虑将设置为的中位数即可，证明显然。