爱站程序员基地noip模拟25\\;solutions
还是wzz的，依旧无法做出，勉勉强强的第一题拿了70pts，感觉自己菜到家了
啥也不会，啥也推不出来。。。。
T1\\;random
这个就是一个打表找规律的题，我首先打表打出来，一个序列中如果有n个逆序对，
那么他的总贡献就是$\\frac{4}{3}n$,题解上是直接统计的一个长为n的序列的总贡献
然后就继续打表，最后就得到了最后的$\\huge\\sum\\limits_{i=1}^\\frac{\\frac{i(i-1)}{3}}$
为啥没拿满分呢，因为不会公式，然后考完之后一化简，直接输出$\\frac{n^2-1}{9}$就好了
注意n，m超级大，先给他俩取个模
AC_code
#include<bits/stdc++.h>using namespace std;#define ll long longconst ll mod=998244353;ll T;ll ksm(ll x,ll y){ll ret=1;while(y){if(y&1)ret=ret*x%mod;x=x*x%mod;y>>=1;}return ret;}ll N;signed main(){scanf("%lld",&T);while(T--){scanf("%lld",&N);printf("%lld\\n",((N%mod)*(N%mod)%mod-1+mod)%mod*ksm(9,mod-2)%mod);}}T2\\;string
这个就是暴力$hash$，考场上忘记$hash$咋写了，暴力取了个模，又WA又T的
所以我向$Varuxn$学习了$unsigned long long$不取模的做法，搞到了40pts
自己学习了题解部分分做法，搞到了$90pts$，虽然别人都只有$70pts$
虽然隔壁的Varuxn卡到了80，还是菜。。。。。。
咱也不知道为啥咱的暴力总是特别快，哈哈哈哈，咱就是牛逼，！！！！！！
90pts
#include<bits/stdc++.h>using namespace std;#define re register int#define ull unsigned long longconst int N=1e5+5;const ull bas=131;char s,c[N*3];int len,n,sum;ull hs,ba,ans;vector<ull> ha;ull f,g;signed main(){scanf("%s",s+1);len[0]=strlen(s+1);for(re i=1;i<=len[0];i++)hs[i]=hs[i-1]*bas+s[i]-\'a\';scanf("%d",&n);ba[0]=1;for(re i=1;i<N;i++)ba[i]=ba[i-1]*bas;for(re i=1;i<=n;i++){scanf("%s",c+sum+1);len[i]=strlen(c+sum+1);//cout<<len[i]<<" "<<sum<<endl;ha[i].resize(len[i]+3);for(re j=sum+1;j<=len[i]+sum;j++)ha[i][j-sum]=ha[i][j-sum-1]*bas+c[j]-\'a\';sum+=len[i];}for(re x=1;x<=len[0];x++){for(re i=1;i<=n;i++){for(re l=1;l<=len[i];l++){ull tmp0=hs[x+l-1]-hs[x-1]*ba[l];ull tmp1=ha[i][l];if(tmp0==tmp1)g[x]++;else break;}for(re r=1;r<=len[i];r++){ull tmp0=hs[x]-hs[x-r]*ba[r];ull tmp1=ha[i][len[i]]-ha[i][len[i]-r]*ba[r];if(tmp0==tmp1)f[x]++;else break;}}}for(re i=1;i<len[0];i++)ans+=f[i]*g[i+1];printf("%llu",ans);}正解吧，把每个小串前缀后缀放到$Trie$上，开两个树，一个存前缀，一个存后缀
还有二分，我们枚举大串的每一个断点，向左右两侧寻找可以匹配的串的个数
这个时候就用到了$trie$，插入的时候，让走过的每一个节点的权值++
跑$dfs$，将每一个节点的权值，下放到儿子节点,顺便吧这个链的$hash$值求出来
将$hash$值和此时的权值放到$map$里，注意用$unordered_map$，这个还快一些
二分断点左右两侧能够匹配的长度，如果手写map的话可以$O(nlogn)$
我这个常数稍微大一些，注意用find函数，别直接用[]慢好多
AC_code
#include<bits/stdc++.h>using namespace std;#define re register int#define ull unsigned long longconst int N=1e5+5;const int bas=131;char s,cc;vector<char> c;ull hs[2],ba;ull f,g,ans;int len,n;struct TRIE{int siz[N*3],son[N*3][30];int seg;unordered_map<ull,int> mp;TRIE(){seg=1;}void ins(int x,int i,int dep){if(dep==c[i].size())return ;int w=c[i][dep]-\'a\'+1;if(!son[x][w])son[x][w]=++seg;siz[son[x][w]]++;ins(son[x][w],i,dep+1);}void dfs(int x,ull ha){mp[ha]=siz[x];//cout<<ha<<" "<<siz[x]<<endl;for(re i=1;i<=26;i++){if(!son[x][i])continue;//cout<<x<<" "<<i<<" "<<ha*bas+i<<endl;siz[son[x][i]]+=siz[x];dfs(son[x][i],ha*bas+i);}}}fro,beh;signed main(){scanf("%s",s);len[0]=strlen(s);scanf("%d",&n);for(re i=1;i<=n;i++){scanf("%s",cc+1);len[i]=strlen(cc+1);for(re j=1;j<=len[i];j++)c[i].push_back(cc[j]);}for(re i=1;i<=n;i++)fro.ins(1,i,0);for(re i=1;i<=n;i++)reverse(c[i].begin(),c[i].end());for(re i=1;i<=n;i++)beh.ins(1,i,0);fro.dfs(1,0);beh.dfs(1,0);ba[0]=1;for(re i=1;i<=len[0];i++){hs[0][i]=hs[0][i-1]*bas+s[i-1]-\'a\'+1;ba[i]=ba[i-1]*bas;}for(re i=len[0];i>=1;i--){hs[1][i]=hs[1][i+1]*bas+s[i-1]-\'a\'+1;}for(re i=1;i<=len[0];i++){/*for(re l=1;l<=len[0]-i+1;l++){ull tmp=hs[0][i+l-1]-hs[0][i-1]*ba[l];if(fro.mp[tmp])g[i]+=fro.mp[tmp];else break;}for(re r=1;r<=i;r++){ull tmp=hs[1][i-r+1]-hs[1][i+1]*ba[r];if(beh.mp[tmp])f[i]+=beh.mp[tmp];else break;}*/ull res;int l=1,r=len[0]-i+1,mid;res=hs[0][i]-hs[0][i-1]*bas;if(fro.mp.find(res)==fro.mp.end())g[i]=0;else{while(l<r){mid=l+r+1>>1;ull tmp=hs[0][i+mid-1]-hs[0][i-1]*ba[mid];if(fro.mp.find(tmp)!=fro.mp.end())l=mid;else r=mid-1;}res=hs[0][i+l-1]-hs[0][i-1]*ba[l];g[i]=fro.mp[res];}//cout<<i<<" "<<l<<" ";l=1;r=i;res=hs[1][i]-hs[1][i+1]*bas;if(beh.mp.find(res)==beh.mp.end())f[i]=0;else{while(l<r){mid=l+r+1>>1;ull tmp=hs[1][i-mid+1]-hs[1][i+1]*ba[mid];if(beh.mp.find(tmp)!=beh.mp.end())l=mid;else r=mid-1;}res=hs[1][i-l+1]-hs[1][i+1]*ba[l];f[i]=beh.mp[res];//cout<<res<<" "<<l<<" "<<endl;//cout<<res<<" "<<l<<endl;}}for(re i=1;i<len[0];i++)ans+=f[i]*g[i+1];//cout<<f[i]<<" "<<g[i]<<endl;printf("%llu",ans);}T3\\;queen
就这，就这，就这啊！！！！
我没压行，而且吧，还把一行拆成两行了，你们不需要缩放页面！！！！
就推个式子，简简单单轻轻松松，题解说的挺明白，你要是想拍啊
就把代码粘走？？？
AC_code(缩放80%）
#include<bits/stdc++.h>using namespace std;#define re register int#define ll long longconst int mod=3e5+7;ll T,n,m,k,ans;ll jc[mod+10],inv[mod+10];ll ksm(ll x,ll y){ll ret=1;x%=mod;while(y){if(y&1)ret=ret*x%mod;x=x*x%mod;y>>=1;}return ret;}ll W(ll x,ll y){if(x<y)return 0;//cout<<inv[y]%mod*inv[(x-y+mod)%mod]%mod<<" "<<ksm(jc[y]*jc[(x-y+mod)%mod]%mod,mod-2)<<endl;return jc[x]*inv[y]%mod*inv[(x-y+mod)%mod]%mod;//return jc[x]*ksm(jc[y]*jc[(x-y+mod)%mod]%mod,mod-2)%mod;}ll C(ll x,ll y){if(x<y)return 0;if(!x||!y)return 1;return C(x/mod,y/mod)*W(x%mod,y%mod)%mod;}signed main(){jc[0]=1;inv[0]=1;for(re i=1;i<=mod;i++)jc[i]=jc[i-1]*i%mod;inv[mod-1]=ksm(jc[mod-1],mod-2);for(re i=mod-2;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;scanf("%lld",&T);while(T--){ans=0;scanf("%lld%lld%lld",&n,&m,&k);ans=(ans+(m%mod)*C(n,k)%mod)%mod;ans=(ans+(n%mod)*C(m,k)%mod)%mod;ll nn=max(n,m),mm=min(n,m);ans=(ans+2*(C(mm+1,k+1)*2+max(nn-mm-1,0ll)%mod*C(mm,k))%mod)%mod;if(n==m)ans=(ans+2*mod-2*C(m,k))%mod;if(k==1)ans=(n%mod)*(m%mod)%mod;if(k==3){ll mi=min(n-1,(m-1)/2);//cout<<ans<<endl;ans=(ans+2*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(m+2*n)%mod*((mi%mod)*((mi+1)%mod))%mod*ksm(2,mod-2)%mod+ksm(3,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;swap(m,n);mi=min(n-1,(m-1)/2);//cout<<ans<<endl;ans=(ans+2*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(m+2*n)%mod*((mi%mod)*((mi+1)%mod))%mod*ksm(2,mod-2)%mod+ksm(3,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;swap(m,n);//cout<<ans<<endl;mi=min(n-1,m-1);ans=(ans+4*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-((m+n)%mod)*(mi%mod)%mod*((mi+1)%mod)%mod*ksm(2,mod-2)%mod+ksm(6,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;}if(k==4){ll mi=min(n-1,(m-1)/2);//cout<<ans<<endl;ans=(ans+2*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(m+2*n)%mod*((mi%mod)*((mi+1)%mod))%mod*ksm(2,mod-2)%mod+ksm(3,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;swap(m,n);mi=min(n-1,(m-1)/2);//cout<<ans<<endl;ans=(ans+2*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(m+2*n)%mod*((mi%mod)*((mi+1)%mod))%mod*ksm(2,mod-2)%mod+ksm(3,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;mi=min((m-1)/2,(n-1)/2);ans=(ans+5*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(2*(m+n)%mod)*(mi%mod)%mod*((mi+1)%mod)%mod*ksm(2,mod-2)%mod+4*ksm(6,mod-2)%mod*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;mi=min(n-1,m-1);ans=(ans+((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-((m+n)%mod)*(mi%mod)%mod*((mi+1)%mod)%mod*ksm(2,mod-2)%mod+ksm(6,mod-2)*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;}if(k==5){ll mi=min((m-1)/2,(n-1)/2);ans=(ans+2*((n%mod)*(m%mod)%mod*(mi%mod)%mod+mod-(2*(m+n)%mod)*(mi%mod)%mod*((mi+1)%mod)%mod*ksm(2,mod-2)%mod+4*ksm(6,mod-2)%mod*(mi%mod)%mod*((mi+1)%mod)%mod*((mi*2+1)%mod)%mod)%mod)%mod;}printf("%lld\\n",ans);}}
