罕见的改完了题
T1 random
一堆概率，一堆函数，一堆递归，一眼不可做，
但它只有一个参数，所以..
熠神本着“只有20太难看“的心态，通过样例三个出规律，口胡了一波$\frac{n^{2}-1}{9}$,
然后他切了，
他切了！
所以只有一个参数的题很可能是个结论，很可能可以打表，不要乱弃。。
正解颓柿子，先列出一个逆序对在长为n的序列中的贡献，然后列出答案的总式子，发现逆序对在长度大于等于二的序列里贡献都是4/3（打表/归纳法），
于是将式子化简，最后可以用等差数列求和公式$\sum_{i=1}^{n}i= \frac{n\left ( n+1 \right )}{2}$和$\sum_{i=1}^{n}i^{2}= \frac{n\left ( n+1 \right )\left ( 2n+1 \right )}{6}$化出O（1）。
code（这种代码真的用看吗：
1 #include<bits/stdc++.h>
2 #define debug exit(0)
3 #define LL long long
4 using namespace std;
5 const LL NN=1e18+5,p=998244353;
6 int T,n;
7 inline LL read(){
8 LL x=0,f=1;
9 char ch=getchar();
10 while(ch<'0'||ch>'9'){
11 if(ch=='-') f=-1;
12 ch=getchar();
13 }
14 while(ch>='0'&&ch<='9'){
15 x=(x<<1)+(x<<3)+(ch^48);
16 ch=getchar();
17 }
18 return x*f;
19 }
20 void write(int x){
21 if(x<0) putchar('-'), x=-x;
22 if(x>9) write(x/10);
23 putchar(x%10+'0');
24 }
25 inline int qpow(LL a,LL b){
26 int res=1; a%=p;
27 while(b){
28 if(b&1) res=1ll*res*a%p;
29 a=a*a%p;
30 b>>=1;
31 }
32 return res;
33 }
34 int main(){
35 T=read();
36 int inv=qpow(9,p-2);
37 while(T--){
38 n=read()%p;
39 write((1ll*n*n%p-1+p)%p*inv%p); putchar('\n');
40 }
41 return 0;
42 }
T1
T2 string
因为把前缀拼到后缀前面而爆零了。。
考虑计算以总串中第i位为结尾的后缀和以第i+1位为开始的前缀个数，二者相乘再求和就是答案。加上哈希70pts。
考虑优化。以总串中第i为结尾的后缀中最长后缀一定可以包含其他后缀，也就是说满足条件的后缀都是最长后缀的后缀。前缀同理
把字符串正反插入两颗trie树，通过DFS统计数量，然后二分找每个点的最长前后缀，记录答案。
code：
1 #include<bits/stdc++.h>
2 #define debug exit(0)
3 #define ULL unsigned long long
4 #define rin register int
5 #define int long long
6 using namespace std;
7 const int NN=2e5+5;
8 const ULL base=131;
9 int n,ls,l,r,pr[NN],ne[NN],tmp,ans;
10 ULL shas[NN],bas[NN],hs;
11 char s[NN],ch[NN];
12 inline int read(){
13 int x=0,f=1;
14 char ch=getchar();
15 while(ch<'0'||ch>'9'){
16 if(ch=='-') f=-1;
17 ch=getchar();
18 }
19 while(ch>='0'&&ch<='9'){
20 x=(x<<1)+(x<<3)+(ch^48);
21 ch=getchar();
22 }
23 return x*f;
24 }
25 void write(int x){
26 if(x<0) putchar('-'), x=-x;
27 if(x>9) write(x/10);
28 putchar(x%10+'0');
29 }
30 inline ULL get(int l,int r){
31 if(l>r) return 0;
32 return shas[r+1]-shas[l]*bas[r-l+1];
33 }
34 struct trie{
35 int to[NN][27],tot;
36 long long siz[NN];
37 ULL has[NN];
38 unordered_map<ULL,int>vis;
39 void insert(char ss[],int op){
40 int len=strlen(ss),root=1;
41 for(int i=0;i<len;i++){
42 int now=ss[i]-'a';
43 if(!to[root][now]){
44 to[root][now]=++tot;
45 if(!op) has[tot]=has[root]*base+(ULL)ss[i];
46 else has[tot]=ss[i]*bas[i]+has[root];
47 }
48 root=to[root][now]; siz[root]++;
49 }
50 }
51 void dfs(int fa,int s){
52 if(!s) return;
53 siz[s]+=siz[fa]; vis[has[s]]+=siz[s];
54 for(int i=0;i<26;i++) dfs(s,to[s][i]);
55 }
56 }nex,pre;
57 signed main(){
58 bas[0]=1; for(rin i=1;i<(NN);i++) bas[i]=bas[i-1]*base;
59 scanf("%s",s); ls=strlen(s);
60 n=read(); nex.tot=pre.tot=1; nex.vis[0]=pre.vis[0]=0;
61 for(rin i=1;i<=n;i++){
62 scanf("%s",ch);
63 pre.insert(ch,0);
64 reverse(ch,ch+strlen(ch));
65 nex.insert(ch,1);
66 }
67 for(rin i=1;i<=ls;i++) shas[i]=shas[i-1]*base+(ULL)s[i-1];
68 nex.dfs(0,1); pre.dfs(0,1);
69 for(int i=0;i<ls;i++){
70 l=0; r=i+1; tmp=0;
71 while(l<=r){
72 int mid=l+r>>1;
73 if(nex.vis.find(get(i-mid+1,i))!=nex.vis.end()) tmp=mid, l=mid+1;
74 else r=mid-1;
75 }
76 ne[i+1]=nex.vis[get(i-tmp+1,i)];
77 l=0; r=ls-i; tmp=0;
78 while(l<=r){
79 int mid=l+r>>1;
80 if(pre.vis.find(get(i,i+mid-1))!=pre.vis.end()) tmp=mid, l=mid+1;
81 else r=mid-1;
82 }
83 pr[i]=pre.vis[get(i,i+tmp-1)];
84 }
85 for(int i=0;i<ls;i++) ans+=ne[i]*pr[i];
86 write(ans); putchar('\n');
87 return 0;
88 }
T2
T3 queen
大力分类讨论，式子倒就那么几个，推出一两个后就很好推了
用到了$\sum_{i=1}^{n}\binom{i}{k}= \binom{n+1}{k+1}$和$\sum_{i=1}^{n}i^{2}= \frac{n\left ( n+1 \right )\left ( 2n+1 \right )}{6}$。
k大于5后只会有直线和斜线的情况，分类讨论k小等5，出题人题解讲的挺不当人清楚的
注意这题范围1e18，组合数的参数不能取模，然后计算时要疯狂%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%才不会爆
code：
1 #include<bits/stdc++.h>
2 #define debug exit(0)
3 #define int long long
4 using namespace std;
5 const int NN=1e18+5,p=3e5+7,inv6=250006,inv2=150004;
6 int T,ans;
7 int n,m,k,inv[p],fac[p];
8 inline int read(){
9 int x=0,f=1;
10 char ch=getchar();
11 while(ch<'0'||ch>'9'){
12 if(ch=='-') f=-1;
13 ch=getchar();
14 }
15 while(ch>='0'&&ch<='9'){
16 x=(x<<1)+(x<<3)+(ch^48);
17 ch=getchar();
18 }
19 return x*f;
20 }
21 void write(int x){
22 if(x<0) putchar('-'), x=-x;
23 if(x>9) write(x/10);
24 putchar(x%10+'0');
25 }
26 inline int qpow(int a,int b){
27 int res=1; a%=p;
28 while(b){
29 if(b&1) res=1*res*a%p;
30 a=a*a%p;
31 b>>=1;
32 }
33 return res;
34 }
35 void init(){
36 fac[0]=inv[0]=1;
37 for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;
38 for(int i=1;i<p;i++) inv[i]=qpow(fac[i],p-2);
39 }
40 inline int C(int n,int m){ if(n<m) return 0; return fac[n]*inv[m]%p*inv[n-m]%p; }
41 inline int lucas(int n,int m){ if(!m) return 1; return C(n%p,m%p)*lucas(n/p,m/p)%p; }
42 inline int sigma1(int x){ return x*(x+1)%p*inv2%p; }
43 inline int sigma2(int x){ return x*(x+1)%p*(2*x+1)%p*inv6%p; }
44 signed main(){
45 T=read(); init();
46 while(T--){
47 n=read(); m=read(); k=read();
48 if(n>m) swap(n,m); int M=m%p,N=n%p,K=k%p;
49 if(k==1){ write(N*M%p); putchar('\n'); continue; }
50
51 ans=((N*lucas(M,K)%p+M*lucas(M,K)%p)%p+(N+M+1)%p*2%p*lucas(N,K)%p-lucas(N+1,K+1)%p*K%p*4%p+p)%p;
52
53 if(k==3){
54 int x=min(n,m/2)%p,y=min(n/2,m)%p;
55 ans=(ans+((M*N%p*(N-1)%p+sigma2(N-1))%p-(M+N)%p*sigma1(N-1)%p+p)*4%p)%p;
56 ans=(ans+(M*N%p*x%p-(2*N+M)%p*sigma1(x)%p+2*sigma2(x)%p+p)*2%p)%p;
57 ans=(ans+(M*N%p*y%p-(2*M+N)%p*sigma1(y)%p+2*sigma2(y)%p+p)*2%p)%p;
58 }
59 if(k==4){
60 int x=min(n,m/2)%p,y=min(n/2,m)%p,z=min(n,m)/2%p;
61 ans=(ans+((M*N%p*(N-1)%p+sigma2(N-1))%p-(M+N)%p*sigma1(N-1)%p+p)%p)%p;
62 ans=(ans+(M*N%p*x%p-(2*N+M)%p*sigma1(x)%p+2*sigma2(x)%p+p)*2%p)%p;
63 ans=(ans+(M*N%p*y%p-(2*M+N)%p*sigma1(y)%p+2*sigma2(y)%p+p)*2%p)%p;
64 ans=(ans+(M*N%p*z%p-2*(M+N)%p*sigma1(z)%p+4*sigma2(z)%p+p)*5%p)%p;
65 }
66 if(k==5){
67 int x=min(n,m)/2%p;
68 ans=(ans+(M*N%p*x%p-2*(M+N)%p*sigma1(x)%p+4*sigma2(x)%p+p)*2%p)%p;
69 }
70 write(ans); putchar('\n');
71 }
72 return 0;
73 }
T3
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.23] 集合 [数学]](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
