考试过程：这次考试，状态不是很好。
T1思路想偏了，一上来我就想用类似于线性筛的思路求出答案，但是有个问题，就是如果(a+b=c,d+e=f)，那么(c+f)得到的值在和其他数字凑数的时候就要排除(a,b,c,d)，但是这个处理很复杂，还需要考虑重复出现的数字的情况，我最终也没有调出来，只拿了暴力分。
T2，我觉得是个矩阵乘法，但是没往这方面仔细想，而且因为T1做题不顺导致我心态有些不好，后面也没什么做题的欲望，就随便写了写式子，没发现什么规律，就拿了个部分分。
T3，我也不知道为啥就是理解错题意了，当时状态真是很迷，我读了10多分钟没有理解题意，再加上前面的做题不顺，这心态直接就炸了，T4更没有思路。
总结：1.不要因为前面的题影响自己的考试心态，先拿到能拿到的分。
2.如果一个题自己思路过于复杂，实现过于困难，那么就要及时换一种思路，那么复杂的思路并且在前两题的情况是基本不可能出现的。
3.不要总是想套路，要根据题来想解题方法。
T1 小L的疑惑
思路：我们要求出最小的不能被这些数凑出来的数，那么经过思考，我们可以发现：我们将数字从大到小排序后，可以凑出的数的值域是连续的。我们只需要判断是否存在一个数满足(a_i>sum_{i-1}+1) ，那么(ans=sum_{i-1}+1)。证明应该是显然的。
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=1e5+10;
int ans,n;
int a[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
signed main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
n=read();
for(re i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
if(a[1]!=1) {printf("1
");}
else
{
ans=a[1]+1;
for(re i=2;i<=n;i++)
{
if(a[i]>ans) break;
ans+=a[i];
}
printf("%lld
",ans);
}
return 0;
}
T2 小L的数列
思路：经过手推式子，我们发现直接转移的话没有什么规律，那么接着观察。发现对于一个(i)，我们只需要知道前面的(k)个值，并且要求的式子全都是形如(f_i^b)的形式，考虑使用矩阵乘法。定义运算(c_{i,j}=prod_{i=1}^{k}f_{i,k} ^{b_{k,j}})，这样我们就成功的将递推数列转化成了矩阵乘法的形式。考虑填系数，我是一次转移一个的做法，(res)矩阵只有一行(k)列，(base)矩阵有(k)行(k)列，
每次将(res)数组更新一位，把新的放在最后面，其他位向右移动即可。
注意一个细节：当我们转移(base)矩阵的时候，因为它要当做指数，所以(a^{bc} imes a^{de}=a^{bc+de})，所以在计算矩阵乘法的时候要将结果相加，并且由费马小定理(a^{p-1})与(1)(mod p)同余，所以给指数取模的时候要模(mod-1).
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int mo=998244353;
int n,k;
int b[204],f[204];
struct mat
{
int a[204][204];
};
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii fm(int d,int z)
{
int out=1;
while(z)
{
if(z&1) out=out*d%mo;
z>>=1;
d=d*d%mo;
}
return out;
}
mat calc_base(mat x,mat y)
{
mat z;
memset(z.a,0,sizeof(z.a));
for(re i=1;i<=k;i++) for(re j=1;j<=k;j++) for(re p=1;p<=k;p++) z.a[i][j]=(z.a[i][j]+x.a[i][p]*y.a[p][j])%(mo-1);
return z;
}
mat calc_res(mat x,mat y)
{
mat z;
for(re i=1;i<=k;i++) for(re j=1;j<=k;j++) z.a[i][j]=1;
for(re i=1;i<=1;i++) for(re j=1;j<=k;j++) for(re p=1;p<=k;p++) z.a[i][j]=z.a[i][j]*fm(x.a[i][p],y.a[p][j])%mo;
return z;
}
iv ksm()
{
mat base,res;
memset(base.a,0,sizeof(base.a));
memset(res.a,0,sizeof(res.a));
for(re i=1;i<=k;i++) res.a[1][i]=f[i];
for(re i=1;i<k;i++) base.a[i+1][i]=1;
for(re i=1;i<=k;i++) base.a[i][k]=b[k-i+1];
int z=n-k;
while(z)
{
if(z&1) res=calc_res(res,base);
z>>=1;
base=calc_base(base,base);
}
printf("%lld
",res.a[1][k]);
}
signed main()
{
freopen("seq.in","r",stdin),freopen("seq.out","w",stdout);
n=read(),k=read();
for(re i=1;i<=k;i++) b[i]=read();
for(re i=1;i<=k;i++) f[i]=read();
if(n<=k) {printf("%lld
",f[n]);return 0;}
ksm();
return 0;
}
T3 连边
这道题我看错题了，边权就是两点之间的距离，因为题目中说了个价值，我就一位距离是(1)。
思路：既然我们要求最小价值，也就是最短距离，那么我们可以把所有黑点位起点跑一遍多源最短路，那么这个(dis)数组的含义就是距离它最近的黑点到他的距离，最后我们记录前驱，去重后将答案累加即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
int n,m,ans,tot;
const int N=2e5+10;
const int INF=1e18;
int to[N<<1],next[N<<1],val[N<<1],head[N];
int dis[N],pre[N],las[N];
bool col[N],vis[N],use[N<<1];
queue<int> Q;
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y,int z)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
val[tot]=z;
}
iv get_pre(int x)
{
if(!x) return;
use[las[x]]=1;
get_pre(pre[x]);
}
iv spfa()
{
for(re i=1;i<=n;i++)
{
if(col[i]) Q.push(i),dis[i]=0,vis[i]=1;
else dis[i]=INF;
}
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(re i=head[x];i;i=next[i])
{
int p=to[i];
if(dis[p]>dis[x]+val[i])
{
dis[p]=dis[x]+val[i];
pre[p]=x;
las[p]=i;
if(!vis[p]) vis[p]=1,Q.push(p);
}
}
vis[x]=0;
}
for(re i=1;i<=n;i++) if(!col[i]) get_pre(i);
for(re i=1;i<=tot;i++) if(use[i]) ans+=val[i];
}
signed main()
{
freopen("minimum.in","r",stdin);
freopen("minimum.out","w",stdout);
n=read(),m=read();
for(re i=1;i<=n;i++) col[i]=read();
int x,y,z;
for(re i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
spfa();
if(ans==0) printf("impossible");
else printf("%lld
",ans);
return 0;
}
T4 小L的有向图
思路：根据数据范围，我们推测可能是状压。那么考虑定义，设(f_i)，表示当前选择的点集为(i)的拓扑序方案数，那么我们枚举一个(j),转移即为(f_{i|(1<<j-1)}+=f_i imes2^{cnt}) ，(cnt)为当前点集中与(j)连边的条数。
这个为啥是(2^{cnt})，可以由二项式定理得出。
((a+b)^n=sum_{k=0}^nC_n^ka^kb^{n-k})
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int M=900;
const int N=23;
const int mo=998244353;
int n,m,tot,ans;
int to[M],next[M],head[N];
int cnt[1<<22];
ll f[1<<22];
int g[N],mi[N+5];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y)
{
g[y]|=(1<<(x-1));
}
ii ksm(ll d,ll z)
{
ll out=1;
while(z)
{
if(z&1) out=out*d%mo;
z>>=1;
d=d*d%mo;
}
return out%mo;
}
ii lowbit(int x) {return x&(-x);}
signed main()
{
freopen("topology.in","r",stdin);freopen("topology.out","w",stdout);
n=read(),m=read();
int U=(1<<n);
int x,y;
mi[0]=1;
for(re i=1;i<=23;i++) mi[i]=mi[i-1]*2ll%mo;
for(re i=1;i<=m;i++)
{
x=read(),y=read();
add(x,y);
}
for(re i=1;i<U;i++)
{
int x=i;
while(x)
{
cnt[i]++;
x-=lowbit(x);
}
}
for(re i=1;i<U;i<<=1) f[i]=1;
for(re i=1;i<U;i++)
{
for(re j=1;j<=n;j++)
{
if(i&(1<<(j-1))) continue;
f[i|(1<<(j-1))]=(f[i|(1<<(j-1))]+1ll*f[i]*mi[cnt[g[j]&i]]%mo)%mo;
}
}
printf("%d
",f[U-1]);
return 0;
}