T1水壶
和名字一样水，双指针移动或者前缀和爆草就行。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline void read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
LL n,k,Max=0,sum[1000005],a;
int main()
{
read(n),read(k);k++;
for (int i=1;i<=n;i++) read(a),sum[i]=sum[i-1]+a;
for (int i=k;i<=n;i++) Max=max(Max,sum[i]-sum[i-k]);
cout<<Max<<endl;
return 0;
}T2魔法值
简单矩阵乘法，设一个$[1*n]$的矩阵$A$里面$A[i]$表示为第X(初始为第0)天的数值，然后设一个$[n*n]$的矩阵$B$，$B[i][j]$表示是否相连，然后矩阵快速幂$B$，最后的$B[i][j]$如果等于$1$就代表需要最后$i$城市的值需要异或上$j$城市的初始值。但是复杂度爆表，那么考虑倍增思想，把$2^i$次变换的$B$矩阵给保存然后倍增调用即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,q,a[2][105],power[105],res[2][105],P[35][105][105];
inline void read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void fac1(LL x)
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
for (int k=1;k<=n;k++)
P[x][i][j]^=(P[x-1][i][k]*P[x-1][k][j]);
}
}
}
inline void fac2(LL x)
{
LL tmp[2][105];
memset(tmp,0,sizeof(tmp));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
tmp[1][i]^=(res[1][j]*P[x][j][i]);
}
for (int i=1;i<=n;i++) res[1][i]=tmp[1][i];
}
int main()
{
read(n),read(m),read(q);
for (LL i=1;i<=n;i++) read(a[1][i]);
for (LL u,v,i=1;i<=m;i++) read(u),read(v),P[0][u][v]=P[0][v][u]=1;
power[0]=1;
for (int i=1;i<=32;i++) fac1(i),power[i]=power[i-1]<<1;
while (q--)
{
LL X;
read(X);
for (int i=1;i<=n;i++) res[1][i]=a[1][i];
for (int i=0;i<=32;i++) if ((X>>i)&1) fac2(i);
cout<<res[1][1]<<endl;
}
return 0;
} T3优秀子序列
设f[i]表示为子序列总和为i时的方案数，这个可以通过满足$((i-a[i])|a[i])=i$的$i-a[i]$推来，可以满足选出来的子序列中的数两两异或为$0$的这一要求。为什么？因为$(i-a[i])|a[i]=i$这一条件如果要成立的话，必须满足$i-a[i]$的所有含$1$位置对应$a[i]$的$0$位置,而$0$的位置$a[i]$随便填$1$或$0$都行，也就满足上面那个条件。如果不满足选出来的子序列中的数两两异或为$0$的这一要求，那么某一位$1$也就被$|$了两次(两个$1$在同一位$|$成一个$1$)，但由于位运算的原因，最后只加上了一个$2^i$所以会导致$((i-a[i])|a[i])<i$。那么这个问题就好解决了，我们枚举一个二进制数为$i$，把它看成整个子序列的总和，那么我们就可以再通过枚举一个子集来确定$a[i]$，最后把两者异或就可以得到该子集的补集$i-a[i]$并且一定满足$((i-a[i])|a[i])=i$，然后记录下每个$a[i]$出现的次数大力推导$DP$即可，注意枚举的时候记得判断子集与补集的大小关系，每个子集与补集只算一次，防止枚举到该子集的补集导致贡献重复计算。另外记得$0$要另外算，因为它不影响选出来的子序列中的数两两异或为$0$的这一要求，所以$0$可以有$2^{tot[0]}$种出现方式在每个无0的子序列中(全0则出现在空集中)所以最后答案要乘上$2^{tot[0]}$。（一开始 🧠 升 级把空集看作$0$和其它$0$都算一起了，后面才发现是不一样的，因为一个子序列跟了不同的$0$是不同的，但跟一个空集本质是一样的，算一种。）
#include<bits/stdc++.h>
#define LL long long
#define Mod 1000000007
using namespace std;
LL n,Max=0,phi[1000005],prime[1000005],cnt=0,f[1000005],tot[1000005],a[1000005];
bool is_prime[1000005];
inline void read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int main()
{
phi[1]=1;
for (LL i=2;i<=300000;i++)
{
if (!is_prime[i]) prime[++cnt]=i,phi[i]=i-1;
for (LL j=1;j<=cnt&&i*prime[j]<=300000;j++)
{
phi[i*prime[j]]=phi[i]*phi[prime[j]];
is_prime[i*prime[j]]=1;
if (i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}
}
}
// for (LL i=1;i<=100;i++) cout<<prime[i]<<" ";
read(n);
for (LL i=1;i<=n;i++) read(a[i]),tot[a[i]]++,Max=max(Max,a[i]),tot[a[i]]%=1000000007;
f[0]=1;f[0]%=1000000007;
LL fac=1;
for (int i=1;i<=tot[0];i++) fac=(fac*2)%1000000007;
LL m=(LL)log2(Max)+1;
for (LL S=1;S<=(1<<m)-1;S++)
{
for (LL E=S;E>=0;E=((E-1)&S)) {if (E>(S^E)) f[S]+=f[S^E]*tot[E],f[S]%=1000000007;if (E==0) break;}
}
long long ans=0;
for (LL i=0;i<=(1<<m)-1;i++) ans=(ans+phi[i+1]*f[i])%1000000007;
cout<<(ans*fac)%1000000007<<endl;
return 0;
}