上紫纪念
A Gennady and a Card Game
题目大意
每个元素有两个值$a,b$，现在你有$5$个元素，问是否有一个元素与给定元素$a$相等或者$b$相等
题解
。
代码
# include<bits/stdc++.h>
using namespace std;
int A,B;
int a[5],b[5];
char s[5][10],qwq[10];
int main()
{
scanf("%s",qwq);
A=qwq[0],B=qwq[1];
for(int i=0;i<5;++i)
{
scanf("%s",s[i]);
a[i]=s[i][0],b[i]=s[i][1];
if(a[i]==A||B==b[i]) return printf("YES\n"),0;
}
return printf("NO\n"),0;
}
B Petr and a Combination Lock
题目大意
给定$n$个角度$a_i$，初始在$0°$位置，第$i$次操作顺/逆时针旋转$a_i°$，问能否在$n$次旋转后回到$0°$的位置
题解
$n$最大才$15$，状态压缩一下表示即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
int n;
int a[21];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
for(int i=0;i<(1<<n);++i)
{
int ans=0;
for(int j=0;j<n;++j)
if(i&(1<<j)) ans+=a[j];
else ans-=a[j];
if(ans%360==0) return puts("YES"),0;
}
return puts("NO"),0;
}
C Yuhao and a Parenthesis
题目大意
给定$n$个括号序列（不一定合法），每次可以选择两个没选过的序列首尾相连合并成一个括号序列，问合并之后最多有多少个合法括号序列
题解
把'('定为$1$，')'定为$-1$，可以记录每个括号序列的总和和最小前缀和，显然)...(这种是不可能组成合法的括号序列的，分总和$>0,=0,<0$三种情况讨论一下即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
int n,ans;
char a[MAX*5];
map<int,int> ma;
int main()
{
scanf("%d",&n);
for(int i=1,_n,w,_w;i<=n;++i)
{
scanf("%s",a),_n=strlen(a),w=0,_w=1e9;
for(int j=0;j<_n;++j)
{
if(a[j]=='(') ++w;
else --w;
_w=min(_w,w);
}
if(!w&&_w>=0)
{
if(ma[w]) --ma[w],++ans;
else ++ma[w];
}
if(w>0&&_w>=0)
{
if(ma[-w]) --ma[-w],++ans;
else ++ma[w];
}
if(w<0&&_w>=w)
{
if(ma[-w]) --ma[-w],++ans;
else ++ma[w];
}
}
return printf("%d",ans),0;
}
D Makoto and a Blackboard
题目大意
给定两个数$n,k$，每次随机选择$n$的某个因子$a$使得$n=a$，问操作$k$次后$n$的期望值
题解
如果$n=p^m$（$p$为素数）就可以直接暴力枚举$m$然后$dp$了
因为$n=p_1^{m_1}\times p_2^{m_2}\times…\times p_l^{m_l}$（对$n$质因子分解），所以答案为$\prod_{i=1}^{l} ans(p_i^{m_i})$，具体为什么不会证……听说好像是跟积性函数有关？管他呢A了就行了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<map>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e4+5,mod=1e9+7;
LL n;
int k,cnt,ans=1;
LL qwq[MAX];
int f[101][MAX];
map<LL,int> ma;
int Pow(LL a,int b)
{
int ans=1;
a%=mod;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*a*ans%mod;
return ans;
}
int dfs(LL A,int x,int t=0)
{
if(f[x][t]) return f[x][t];
if(t==k) return Pow(A,x);
int ans=0;
for(int i=0;i<=x;++i)
ans=(ans+dfs(A,i,t+1))%mod;
return f[x][t]=1ll*ans*Pow(x+1,mod-2)%mod;
}
int main()
{
cin>>n>>k;
for(int i=2;i<=sqrt(n);++i)
while(n%i==0)
{
if(++ma[i]==1) qwq[++cnt]=i;
n/=i;
}
if(n!=1) if(++ma[n]==1) qwq[++cnt]=n;
for(int i=1;i<=cnt;++i)
memset(f,0,sizeof(f)),ans=1ll*ans*dfs(qwq[i],ma[qwq[i]])%mod;
return printf("%d",ans),0;
}
E Egor and an RPG game
F Alex and a TV Show
题目大意
给定$n$个初始为空的集合（可重集），有四个操作：
- 给定集合位置$x$和一个数$v$，然后$S_x={v}$
- 给定集合位置$x,y,z$，然后$S_x=S_y∪S_z$
- 给定集合位置$x,y,z$，然后$S_x={\gcd(a,b)\vert a\in S_y,b\in S_z}$
- 给定集合位置$x$和一个数$v$，然后输出集合$x$中有多少个$v$，答案$\%2$
题解
用$f_{x,i}$表示集合$S_x$中$i$的倍数出现次数的奇偶性，可以用bitset维护
因为值域才$7000$，操作一可以直接$\sqrt{n}$枚举修改
操作二发现都是$1$的时候答案是$0$，都是$0$的时候答案是$0$，一个是$0,1$的时候答案是$1$，所以就是一个异或操作
操作三发现都是$1$的时候答案是$1$，都是$0$的时候答案是$0$，一个是$0,1$的时候答案是$0$，所以就是一个与操作
操作四可以莫比乌斯反演一下：
设$F_{x,i}$表示集合$S_x$中$i$的出现次数，则有
$f_{x,i}=\sum_{i\vert j}F_{x,j}$
$F_{x,i}=\sum_{i\vert j}\mu(\frac{j}{i})f_{x,j}$
因为$f_{x,i}$只有$0/1$两种取值，所以$\mu$的值为$-1$和$1$没有区别，预处理一下即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<bitset>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,N=7e3+5;
int n,q,tot;
int u[N],pm[N];
bool use[N];
bitset<N> a[MAX],b[N],w[N];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),q=read(),u[1]=1;
for(int i=2;i<N;++i)
{
if(!use[i]) pm[++tot]=i,u[i]=-1;
for(int j=1;j<=tot&&i*pm[j]<N;++j)
{
use[i*pm[j]]=1;
if(i%pm[j]==0) break;
u[i*pm[j]]=-u[i];
}
}
for(int i=1,x;i<N;++i)
{
x=sqrt(i);
for(int j=1;j<=x;++j)
if(i%j==0) w[i][j]=w[i][i/j]=1;
}
for(int i=1;i<N;++i)
for(int j=i;j<N;j+=i)
if(u[j/i]) b[i][j]=1;
for(int i=1,op,x,y,z;i<=q;++i)
{
op=read(),x=read(),y=read();
if(op==1) a[x]=w[y];
else if(op==2) z=read(),a[x]=a[y]^a[z];
else if(op==3) z=read(),a[x]=a[y]&a[z];
else if(op==4) printf("%d",(a[x]&b[y]).count()%2);
}
return 0;
}
