http://zhengruioi.com/contest/1005

预计 \(100+25+0+100=225\)
实际 \(100+25+0+40=165\)
不取模挂飞了

A.数字变换

你有一个素数 \(p\) 和二元组 \((a,b)\)，它们的和不被 \(p\) 整除。
每一步，你可以二元组做如下操作中的一个：

• 把 \((a,b)\) 变成 \((2a \bmod p,(b+p−a)\bmod p)\)
• 把 \((a,b)\) 变成 \(((a+p−b)\bmod p,2b\bmod p)\)

你需要回答 \(q\) 次询问，每次询问，给你 \(ai,bi,ci,di\)，问最少需要多少步能将 \((ai,bi)\) 变成 \((ci,di)\)。如果不可行，那么输出 \(−1\)。
\(q\le 10^5,p\le 10^9+7\)

\(a+b\bmod p\) 的值不变，所以只考虑 \(a_i\)，若 \(a_i=c_i\) 则自然有了 \(b_i=d_i\)
考虑枚举答案 \(k\)，此时 \(a'\) 可能的取值为 \((2^k-u)a-ub,u\in [0,2^k)\)，当 \(2^k>p\) 了必然有解，所以枚举 \(k\) 判断即可

long long mod;
int q;
inline long long power(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
int main(){
	mod=read();q=read();
	while(q--){
		long long a=read(),b=read(),c=read(),d=read();
		if(a>b) std::swap(a,b),std::swap(c,d);
		if(a==c&&b==d){puts("0");continue;}
		if((a+b)%mod!=(c+d)%mod){puts("-1");continue;}
		if(mod==2){puts("1");continue;}
		long long invab=power((a+b)%mod,mod-2);
		int sobig=0;
		for(int k=2,ans=1;;){
			long long n=(c+k*b%mod)%mod*invab%mod;
			if((n>k&&!sobig)||(!n&&!sobig)) goto CONTINUE;
			if(((k-n+1)*b%mod-(n-1)*a%mod+mod)%mod==d||1){
				printf("%d\n",ans);break;
			}
		CONTINUE:;
			ans++;
			if(k*2>=mod) sobig=1;
			k=k*2%mod;
		}
	}
	return 0;
}

B.均分财产

有 \(n\) 个数，你希望能删除其中不超过 \(k\) 个数，然后将剩下的数划分成两个子集（可以有重复的数字），满足这两个子集中的数的和是相等的。
为了降低出题和做题的难度，可以认为这 \(n\) 个数都是在 \(1\) 到 \(W\) 内随机的。
\(n\le 2\times 10^5,\min(25,n-2)\le k\le n-2,W=2\times 10^5\)

若 \(n\le 25\) 只需暴力枚举所有子集，找两个和相同即可（减去并）
否则，对于前 \(n-25\) 个，从大到小枚举，当前和大于 \(0\) 就减去，否则加上，最后和为 \(x\)，则有 \(|x|\le W\)
对于剩下的 \(25\) 个爆搜出两个差为 \(x\) 的子集即可
由于子集共 \(2^{25}\) 个，远大于 \(26W\)，所以几乎一定为由相差 \(x\) 的子集

C.查询工资

蔡老板有很多个员工，蔡老板的工号是 \(1\)，剩下的 \(n−1\) 个员工的工号分别为 \(2,3,\cdots,n\)，对于第 \(i(2\le i\le n)\) 号员工，有个直属上司 \(f_i(1\le fi<i)\)
蔡老板想知道所有员工的工资，但是他不能直接问，所以他可以做这样的询问：

• 对于一个员工，如果他的直接下属（也就是儿子）个数不小于 \(k\) 个，可以询问他所有直接下属的工资和。
• 对于一个员工，如果他的直接或间接的下属（也就是子树里面所有点，不包括自己）个数不小于 \(k\) 个，可以询问他所有下属（不包括自己）的工资和。

蔡老板想知道，如果只通过这两种询问，进行任意多次之后，能知道哪些员工具体的工资。也就是通过上述的信息加上一系列加减法运算，可以计算出这个人的工资。
蔡老板还可以开人，如果一个人没有直接下属，就可以被开除。蔡老板可以不停执行这个操作。也就是不停的选择叶子节点删除，如果一个节点的儿子被删完了，那么它也可以被删除。
蔡老板想知道一个开除员工的方案，使得开除完员工之后，在剩下的员工里，用上面的查询，能知道尽量多的人的工资。
\(n\le 8\times 10^5,2\le k\le 10^5\)

考虑如果某点的父亲不只有他一个儿子，则无论如何询问，他们都在一起被计算，必定无法区分
对于没有兄弟的点：

#define N 800006
#define M 800006
struct Graph{
	int nex[M],to[M],fir[N];
	int tot;
	inline void add(int u,int v){
		to[++tot]=v;
		nex[tot]=fir[u];fir[u]=tot;
	}
}G;
int n,k;
int f[N],size[N];
void dfs(int u){
	size[u]=1;f[u]=0;
	int son=0,ff=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];son++;
		dfs(v);
		size[u]+=size[v];f[u]+=f[v];
		ff|=(size[v]>=2&&!f[v]);
	}
	if(ff&&son>=k) f[u]++;
	for(int i=G.fir[u];i;i=G.nex[i])if(size[G.to[i]]>=k+1) f[u]=std::max(f[u],f[G.to[i]]+1);
}
int main(){int $=read();while($--){
	n=read();k=read();
	std::memset(G.fir,0,(n+1)*sizeof G.fir[0]);G.tot=0;
	for(int i=2;i<=n;i++) G.add(read(),i);
	dfs(1);
	printf("%d\n",f[1]);
}
	return 0;
}

D.多项式题

没取模爆成 40 了/px

#define N 200006
#define mod 998244353
int n;
char s[N];
long long f[N],sum[N],power[N];
int main(){
	n=read();
	scanf("%s",s+1);
	sum[1]=f[1]=s[1]-'0';
	power[0]=1;power[1]=10;
	for(int i=2;i<=n;i++) sum[i]=(sum[i-1]*10+s[i]-'0')%mod,power[i]=power[i-1]*10%mod;
	long long S=(s[1]-'0')*(s[2]-'0'),ss=s[1]-'0';
	for(int i=2;i<=n;i++){
		f[i]=(sum[i]+S)%mod;
		S=(S*10%mod+ss*(s[i+1]-'0')%mod+f[i]*(s[i+1]-'0')%mod)%mod;
		ss=(ss+f[i])%mod;
	}
	printf("%lld\n",f[n]);
	return 0;
}