前言
是比赛，我死了
前两道同进制转化有关，后一道不会
被一大批比我小还比我强的人吊打
暴力打锅了 65 pts，最后只剩 65pts
qwq
T1
题意
给你一个复数，它的实部和虚部都是 $1e18$ 以内的整数，求其分解为$p=-1-i$ 的多个不同次幂的和，输出次幂即可
题解
发现给出复数，可以分解为$p^{k_1}+p^{k_2}+\cdots+p^{k_s}$ ，且 $k_1<k_2<\cdots<k_s$
通过打表，我们可以发现，对于 $p^k$ 只有当 k=1 时，其虚部和实部都为奇数，同时当 k=200 时，其实部和虚部都超出了 $1e18$ ，所以我们考虑将给出的复数不断除以$p$ ，当其实部和虚部都为奇数时，则说明当前序列第一项为 $p$ ,我们记录下除以 $p$ 的次数，记录答案后减去 $p$
一直重复上述过程直至其虚部和实部都为 $0$
特判一下 $k_1=0$ 的情况
代码
comp t=(comp){x=read(),y=read()};
comp p=(comp){-1,-1};
if((t.x&1)^(t.y&1))ans[++tot]=0,t.x-=1;
int cnt=1;
while(t.x||t.y)
{
if((t.x&1)||(t.y&1))
{
ans[++tot]=cnt;
t=t-p;
}
t=t/p;
++cnt;
}
printf("%d\n",tot);
for(register int i=1;i<=tot;++i)printf("%lld\n",ans[i]);
return 0;总结
考试的时候想过 $p$ 进制下分解的唯一性，但没想到除法这方面
还分了 subtaxk 打暴力，结果少打了一个 return 0 暴力 50pts->25pts
qwq
T2
题意
给定一个长度为 $n$ 的整数序列 $a_1,a_2,a_3,\dots,a_n$ ，求多少个长度 $s>1$ 的子序列 $a_{k_1},a_{k_2},\dots,a_{k_s}$ 满足 $\left( \frac{a_{k_1}}{a_{k_2}}\right)\times\left( \frac{a_{k_2}}{a_{k_3}}\right)\times\cdots\times\left( \frac{a_{k_{s-1}}}{a_{k_s}}\right) \mod 2333>0$
其中 $\left(\frac{n}{m}\right)$ 表示组合数
输出方案数对 $1e9+7$ 取模
题解
2333 是个质数，我们由卢卡斯定理可以得到 $\left(\frac{n}{m}\right)\equiv \left(\frac{n \mod 2333}{m \mod 2333}\right)\cdot\left(\frac{n\text{÷}2333}{m\text{÷}2333}\right)\mod 2333$
我们只要保证对于所有的 $a_k$ 满足
$$
a_k >a_{k+1} \mod 2333\qquad, a_k\text{÷}2333>a_{k+1}\text{÷}3333
$$
由于是选取子序列，我们倒叙枚举，用二维树状数组记录符合条件的方案数即可
代码
inline void insert(int x,int y,ll d){for(register int i=x;i<=2333;i+=i&-i)for(register int j=y;j<=2333;j+=j&-j)tr[i][j]=(tr[i][j]+d)%p;}
inline int query(int x,int y){ll res=0;for(register int i=x;i;i-=i&-i)for(register int j=y;j;j-=j&-j)res=(tr[i][j]+res)%p;return res;}
signed main(void)
{
n=read();
for(register int i=1;i<=n;++i)mxx=max(mxx,a[i]=read());
for(register int i=n;i;--i)
{
int qq=a[i]/2333+1,wq=a[i]%2333+1;
ll t=query(qq,wq);
ans=(ans+t)%p;
insert(qq,wq,t+1);
}
printf("%lld\n",ans);
}总结
考试时没想到卢卡斯定理，只打了 $a_i<2333$ 的 subtask ，然后
然后没对每个数+1，导致树状数组下标从 $0$ 开始 50pts->10pts
qwq
T3
不会
