A 水壶
前缀和即可
B 魔法值
非正解：求图的循环节，然后直接数数数，就好了，有 (70pts)
我们发现这个题目写的运算：
[f_i=xor_ {(i,j)in E} f_j
]
这东西很像矩阵乘法对吧：
(A) 为 (1 imes n) 的 (f) 矩阵
(B) 为 图上的边的矩阵，(n imes n)
一次操作就是 (A imes B)
这里乘法变成异或运算就好了
但是考虑到原题中的数据范围很不友好，得预处理二进制优化
对应询问类快速幂求法即可
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=210;
int n,m,T,f[N],ans[N];
struct mat{
int a[N][N];
int* operator[](int x){return a[x];}
inline void clear(){return memset(a,0,sizeof(a)),void();}
}g[N];
inline mat mul(mat a,mat b)
{
mat res; res.clear();
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) res[i][j]^=(a[i][k]&b[k][j]);
return res;
}
inline void calc(int x)
{
int t[N]={0};
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j) if(g[x][i][j]) t[i]=t[i]^ans[j];
} for(int i=1;i<=n;++i) ans[i]=t[i];
return ;
}
signed main()
{
n=read(); m=read(); T=read();
for(int i=1;i<=n;++i) f[i]=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read();
g[0][y][x]=g[0][x][y]=1;
}
for(int i=1;i<=35;++i) g[i]=mul(g[i-1],g[i-1]);
while(T--)
{
for(int i=1;i<=n;++i) ans[i]=f[i];
int x=read();
for(int i=0;i<=31;++i) if(x&(1<<i)) calc(i);
cout<<ans[1]<<endl;
}
return 0;
}
}
signed main(){return yspm::main();}
C 优秀子序列
莫名看了题不敢想系列
然后发现这题可以想……
把题转化成求 (or) 和为 (i) 的方案数，设为(f_i)，然后求个 (f_i imesvarphi(i))
先干点别的：把 (0) 处理掉，把数字桶排好，筛 (varphi)
然后我们把式子写写：(f_i=f_{i-x} imes app_x)
对于每个数字，我们枚举补集的子集就好了
又是个位运算 (dp)
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=3e5+10,mod=1e9+7;
int app[N],cnt,phi[N],pri[N],x,n,maxx,f[N],res,m;
inline void prework()
{
phi[1]=1;
for(int i=2;i<N;++i)
{
if(!phi[i]) phi[i]=i-1,pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<N;++j)
{
if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
else{phi[i*pri[j]]=phi[i]*pri[j]; break;}
}
} return ;
}
inline int ksm(int x,int y)
{
int res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod;
return res;
}
signed main()
{
prework(); n=read(); for(int i=1;i<=n;++i) x=read(),app[x]++,maxx=max(maxx,x);
f[0]=1; res=ksm(2,app[0]);
n=1; while(n<=maxx) n<<=1; m=1;
for(int i=1;i<=200000;++i)
{
if(!app[i]) continue;
m|=i; int s=m^i;
for(int t=s;;t=(t-1)&s)
{
f[i|t]=(f[i|t]+f[t]*app[i]%mod)%mod;
if(!t) break;
}
}
int ans=0;
for(int i=0;i<n;++i) ans+=f[i]*phi[i+1]%mod,ans%=mod;
cout<<ans*res%mod<<endl;
return 0;
}
}
signed main(){return yspm::main();}
总结
比赛写挂了 (B)
然后可能连成绩证明都没有了
以后可能得找点大数据拍一拍
对于某些奇妙性质的运算，要敏感一下呀！（比如矩阵乘法）
关于 (C) 找点枚举子集的题目看看吧