应该仍然是\(SHOI\)专场
只写了两篇题解，另外两道题都有些超出知识范围了，当然第四题可以学一学改一改。
T1 门票
一道链表哈希，理论\(map\)也能过，但是常数太大了，还是不足以过了这道题，剩下的应该都是模板了，贴代码就行
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+100;
const int MOD=2147493;
int nex[maxn],cnt,head[maxn],key[maxn];
int find(int x)
{
int p=x%MOD;
key[++cnt]=x;
if(!head[p])
{
head[p]=cnt;
return 0;
}
for(int i=head[p];i;i=nex[i])
{
if(key[i]==x)
return 1;
if(nex[i]==0)
{
nex[i]=cnt;
return 0;
}
}
}
int a,b,c,rec=1;
int main()
{
scanf("%d%d%d",&a,&b,&c);find(1);
for(int i=1;i<=2000000;++i)
{
rec=(1ll*rec*a+rec%b)%c;
if(find(rec)){printf("%d",i);return 0;}
}
printf("-1");
return 0;
}
T2 二重镇
六进制状态压缩，显然是不会的，手写六重循环，比较适合放弃
T3 超级跳马
很明显的一个\(dp\)，但是更加明显的是\(dp\)一定只能拿部分分了，因为\(2\leq m \leq 10^9\)
实际上\(dp\)的时候也是比较讲究的，首先不能直接三重循环嗯枚举之前所有可以到达当前点的点的\(dp\)值，而是要统计前缀和的，那样连部分分都拿不全；其次是不好用"行"来作为\(dp\)的阶段，以为这样就会用没有计算的阶段来更新当前的答案，反正我是用列来作为状态的。先贴一个\(50pts\)的代码吧
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int MOD=30011;
int n,m;
int dp[300000][52],sum[300000][52];
signed main()
{
scanf("%lld%lld",&n,&m);
dp[1][1]=1,sum[1][1]=1;
for(register int j=2;j<=m;++j)
{
for(register int i=n;i>=1;--i)
{
dp[j][i]=(dp[j][i]+sum[j-1][i])%MOD;
dp[j][i]=(dp[j][i]+sum[j-1][i+1])%MOD;
dp[j][i]=(dp[j][i]+sum[j-1][i-1])%MOD;
sum[j][i]=(sum[j][i]+sum[j-2][i]+dp[j][i])%MOD;
}
}
printf("%lld",dp[m][n]);
return 0;
}
/*
printf("dp:\n");
for(register int j=1;j<=m;++j)
{
for(register int i=n;i>=1;--i)
printf("%d ",dp[j][i]);
printf("\n");
}
printf("sum:\n");
for(register int j=1;j<=m;++j)
{
for(register int i=n;i>=1;--i)
printf("%d ",sum[j][i]);
printf("\n");
}
*/
然后想到了\(dp\)之后，又有如此大的数据范围，就不难想到正解就是用矩阵来优化递推了，实际上题目中也是有暗示这一点的，那就是在\(m\)的逆天范围情况下,\(n\)最大也只有\(50\)
一个很重要的领悟
以前以为矩阵只限于开一个很小的矩阵（顶多几行几列的那种），然后做线递推，但是这样到了递推式为二维的时候，就完全束手无策了
实际上我们可以写一个很大的矩阵(把某一维或者很多维的\(1-n\)所有项都写在一个矩阵内，然后嗯转移)
就像这道题，我们写出来的矩阵就是:
注意到对于任意一个点，走一步能直接到达的就是他上面的三个点\(dp_{i,j}+=dp_{i-1,j-1}+dp_{i,j-1}+dp_{i+1,j-1}\)，而对于其他所有能走奇数步数到达当前点的点，它们一定能到达当前点正上方两步的点，所以它们一定都通过走奇数步之后再走两步（仍然是奇数步），到达当前点。即\(dp_{i,j}+=dp_{i,j-2}\)，但是注意！！我们并不是直接通过这个隔了两步的点走到当前点的，而是把它作为一个中间辅助点，在它之前有点的时候才能统计答案（下文会提到）。
转移矩阵就是对应着递推式\(dp_{i,j}=dp_{i-1,j-1}+dp_{i,j-1}+dp_{i+1,j-1}+dp_{i,j-2}\)写了，当然他的大小是和\(n\)有关系的，有一点点大：
值得注意的是这个矩阵是需要我们用\(for\)循环分成四个块来构造的
这个时候你写出了初始矩阵（从第二项开始）然后高高兴兴的写完快速幂，跑出来发现并不是这个答案，然后又回到了之前缀和优化\(dp\)打出来的表，你发现你以为用矩阵求出来是\(dp\)的式子结果是\(sum\)前缀和？？（见下图//这里输出的矩阵\(n,m\)是反转的）:
这时候我们回到\(dp_{i,j}=dp_{i-1,j-1}+dp_{i,j-1}+dp_{i+1,j-1}+dp_{i,j-2}\)的递推式，我们惊奇的发现，在\(dp\)的第三行第四列，我们得到的值竟然不满足上面的递推式了，如果把这个值换成应该递推出来的值（\(2\rightarrow 3\)），每一项就神奇的对应上了我们前缀和优化\(dp\)中前缀和的值了（纯属巧合）。
为什么呢？因为在推这个值的时候，它对应的\(dp_{i,j-2}\)并不是由递推得到的，而是一个初值，这就要说到我们上文提过的“而是把它作为一个中间辅助点，在它之前有点的时候才能统计答案”了，第一行第四个点实际上根本就不是由任何点转移来的，所以它不能在“\(dp_{i,j-2}\)”的情况下参与统计，因此我们把第三行作为初始矩阵，就能解决这个问题了，当然前缀和也是能做得，只要做减法就行了，就像下面一样
点击查看代码
#include<bits/stdc++.h>
#define re register
using namespace std;
struct Matrix{int n,m,v[110][110];Matrix(){memset(v,0,sizeof v);};};
const int MOD=30011;
Matrix operator *(Matrix a,Matrix b)
{
Matrix tmp;tmp.n=a.n,tmp.m=b.m;
for(re int i=1;i<=a.n;++i)
for(re int j=1;j<=b.m;++j)
for(re int k=1;k<=a.m;++k)
tmp.v[i][j]=(tmp.v[i][j]+a.v[i][k]%MOD*(b.v[k][j]%MOD))%MOD;
return tmp;
}
Matrix base(int x)
{
Matrix tmp;tmp.n=tmp.m=x;
for(re int i=1;i<=x;++i)tmp.v[i][i]=1;
return tmp;
}
Matrix Mpower(Matrix a,int b)
{
Matrix ans=base(a.n);
while(b)
{
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
Matrix build(int n)
{
Matrix tmp;tmp.n=tmp.m=2*n;
for(re int i=1;i<=n;++i)
{
tmp.v[i][i]=1;
if(i-1>=1)tmp.v[i][i-1]=1;
if(i+1<=n)tmp.v[i][i+1]=1;
}
for(re int i=1;i<=n;i++)tmp.v[i][i+n]=tmp.v[i+n][i]=1;
return tmp;
}
void pre(Matrix &a,int n)
{
a.n=2*n,a.m=1;
a.v[1][1]=1;
if(n>=2)a.v[2][1]=1;
a.v[n+1][1]=1;
}
int main()
{
re int n,m;
scanf("%d%d",&n,&m);
Matrix ans,sup=build(n);pre(ans,n);
if(m==2)
{
printf("%d",ans.v[n][1]);
return 0;
}
if(m==1)
{
if(n==1)printf("1");
else printf("0");
return 0;
}
ans=Mpower(sup,m-3)*ans;
re int rec=ans.v[2*n][1];
ans=sup*ans;
printf("%d",(ans.v[n][1]-rec+MOD)%MOD);
return 0;
}
最后还要注意特判\(m\)哦