「考试总结」2022-02-06
A.我醉
分奇数和偶数二分回文串长度，判断是不是存在使用点分治
现在问题是判断是不是存在一个跨过当前分治重心的长度为 \(\rm len\) 的回文串，可以先扫出来每个联通块中心到根正向/反向的哈希值
再扫一次联通块里面的每个点，求出来剩下需求的长度 \((len-dep)\) 中是不是有和自己根链上相同哈希值的串，再判断自己根链上剩下的一部分是不是回文串即可
直觉上是 \(3\) 个 \(\log\)，不太能跑过，所以乱搞做法就是随机一个排列，逐个枚举点作为回文串中心，暴力判断是不是可以扩展
Code Display
const int N=2e5+10;
int tim,mark[N],n,id[N];
vector > G[N];
unordered_mapmp,dou;
inline int solve(int cen){
mark[cen]=++tim;
vector > now,pre;
for(auto e:G[cen]) now.emplace_back((ull)e.sec,e.fir,e.fir),mark[e.fir]=tim;
for(int len=0;len<2*n;++len){
mp.clear(); dou.clear();
swap(now,pre); now.clear();
for(auto tmp:pre){
int top,nowt;
ull hs;
tie(hs,top,nowt)=tmp;
if(!mp.count(hs)) mp[hs]=top;
else if(mp[hs]!=top) dou[hs]=1;
}
for(auto tmp:pre){
int top,nowt;
ull hs;
tie(hs,top,nowt)=tmp;
if(dou[hs]) now.emplace_back(tmp);
}
if(!now.size()) return len;
swap(now,pre); now.clear();
for(auto tmp:pre){
int top,nowt;
ull hs;
tie(hs,top,nowt)=tmp;
for(auto e:G[nowt]){
int t=e.fir; if(mark[t]==tim) continue;
mark[t]=tim;
now.emplace_back(hs*133331+(ull)e.sec,top,t);
}
}
} return 2*n;
}
mt19937 Rand(260823);
signed main(){
freopen("name.in","r",stdin); freopen("name.out","w",stdout);
n=read();
for(int i=1;i=5.97) break;
}
print(ans);
return 0;
}
B.梧桐依旧
将所有满秩的 \(n\) 阶矩阵视作一个群 \(G\)，那么原问题就是求解在群 \(G\) 作用下的不动点个数
根据 \(\rm Burnside\) 引理：
\[|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]也就是说等价类个数等于不动点个数的平均值，那么不动点总数就是等价类个数乘群的大小
第一个部分就是求满秩矩阵的个数，本质上就是选出来 \(n\) 个线性无关的向量的方案
选择第一个向量时方案是 \(p^n-1\)，因为这个前面的向量所形成的维度是 \(0\),所以这个向量可以向任意方向扩展（也就是说 \(\rm Vec_i\in [0,p-1]\) 即可），同时不能是 \(0\) 向量
在选择第二个向量的时候不能和第一个向量线性相关，也就是 \(\rm Vec_2=\lambda Vec_1\),而 \(\lambda\) 的选值是 \([0,p-1]\)，所以方案数是 \(p^n-p\)
那么第三个向量的选值方案数和上面类似，这里 \(\lambda\) 有 \(2\) 个，所以不合法方案是 \(p^{2}\)，选向量的方案数是 \(p^{n}-p^{2}\)
依次类推，群的大小就是 \(\prod\limits_{i=0}^{n-1}p^{n}-p^i\)
剩下要求的就是等价类个数，这里有一个结论是左乘矩阵等价于做初等行变换，即 \(B\) 左乘 \(A\) 的含义就是将矩阵 \(B\) 的第 \(i\) 行乘 \(A_{i,j}\) 加到第 \(j\) 行上（\(i=j\) 时附加系数是 \(A_{i,i}-1\)）
那么这里所有形式的初等行变换就可以视作一个置换群
不难发现秩不同的矩阵一定不在一个等价类 \(\{A\}\) 中，那么枚举矩阵的秩 \(k\) 逐个计算
考虑对于一个特定的秩 \(k\)，矩阵的个数的计算是和群大小计算类似的 \(\prod_{i=0}^{k-1}p^n-p^i\)，只考虑线性无关的这些行就行了
接下来计算 \(k\times k\) 的行变换 \(\{B\}\) 种数，这个和数一个 \(k\) 阶满秩矩阵是等价的，所以方案数是 \(\prod\limits_{i=0}^{k-1} p^k-p^i\)
考虑一个可重集合 \(\{C\}\) ，其中元素满足 \(\rm yx(x\in A,y\in B)\) 形式,不难发现这就是特定秩的矩阵总数，那么发现其每个 \(\{A\}\) 中的元素都在 \(\{C\}\) 出现了 \(|\{B\}|\) 次，这是因为全集是每个等价类是通过不同行变换得到的
不要漏记了全 \(0\) 矩阵作为一个等价类！
综上所述:答案为
\[\prod_{i=0}^{n-1}p^n-p^i\left(1+\sum_{i=1}^{n}\prod_{j=0}^{i-1}\frac{p^n-p^j}{p^i-p^j}\right) \]发现分子是一段 \(p^{k}-1\) 的后缀乘积，分母是前缀乘积，所以先算后缀积，再维护前缀积的逆元就可以 \(\Theta(n)\) 做了
Code Display
const int N=3e7+10;
int pre[N],suf[N],pw[N],n,p;
signed main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=read(); p=read();
pw[0]=1; rep(i,1,n) pw[i]=mul(pw[i-1],p);
int siz_G=1;
for(int i=0;i=1;--i) suf[i]=mul(suf[i+1],del(pw[i],1));
pre[n]=ksm(suf[1],mod-2);
Down(i,n,2) pre[i-1]=mul(pre[i],del(pw[i],1));
for(int i=1;i<=n;++i) ckadd(sum,mul(suf[n-i+1],pre[i]));
print(mul(siz_G,sum));
return 0;
}
C.卿且去
将 \(\texttt{(整数,倍数})\) 定义为偏序集，这里可比就是 \(x|y\)，反之不可比
那么原题中 选出来一组质数之后 就是要求得到集合的最长反链，使用 就可以知道是要求最小的链划分
这时候可以贪心得到选数字策略：每次选出来当前集合里面最小的数 \(x\)，并取 \(x,2x,4x\dots\) 作为一组新的链划分
按照上述策略证明这些数字都没被覆盖过是容易的，同时如果在选择 \(x\) 之后不选择 \(2x\) 那么 \(2x\) 又要新开一组链来覆盖之，所以该策略一定能得到最小链划分也是正确的
问题至此变成了按上述策略拆集合后链划分的总数量，将每个划分的 \(1\) 的贡献挂到链首元素处，再考虑每个整数 \(x\) 的贡献：
简记 \(\pi(n)\) 为 \(\le n\) 的奇数个数，\(\omega(x)\) 表示 \(x\) 的质因子个数
-
\(x\in\{\rm odd\}\) 那么只要选出其因子的一个就会产生贡献，数值是 \(2^{\pi(n)-\omega (x)}(2^{\omega(x)}-1)\)
-
\(x\) 是偶数但是不是 \(4\) 的倍数时，如果 \(x\) 的质因子中有且只有 \(2\) 在挑出来的质数集合中那么贡献，否则不贡献，这等价于钦定了 \(x\) 的每个质因子出现在 "挑出来的质数集合" 与否，而对其它因子是否出现并不关注，所以方案数为 \(2^{\pi(n)-\omega (x)}\)
问题转化成了求奇数的 \(\frac{1}{2^{\omega(x)}}\) 的前缀和，\(\frac 1{2^{\omega(x)}}\) 显然是积性函数，使用 \(\rm min25\) 筛即可
Code Display
const int N=6e6+10;
int n,pin=-1;
namespace Min_25{
int pri[N/10],g[N],cnt,Basnum,id1[N],id2[N],tot,R[N],block;
bool fl[N];
inline int getid(int x){return x<=block?id1[x]:id2[n/x];}
inline int S(int n,int i){
if(pri[i]>=n) return 0;
int sum=del(g[getid(n)],mul(Basnum,i-1));
for(int j=i+1;j<=cnt&&pri[j]*pri[j]<=n;++j){
int prd=pri[j],Enum=1;
while(n>=prd){
ckadd(sum,mul(Basnum,add(Enum!=1,S(n/prd,j))));
Enum++;
prd*=pri[j];
}
}
return sum;
}
inline int solve(int NN,int basnum){
tot=cnt=0;
memset(pri,0,sizeof(pri));
memset(g,0,sizeof(g));
memset(id1,0,sizeof(id1));
memset(id2,0,sizeof(id2));
memset(R,0,sizeof(R));
memset(fl,0,sizeof(fl));
n=NN; Basnum=basnum; block=sqrt(n);
for(int i=2;i<=block;++i){
if(!fl[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i<=block;++j){
fl[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(int l=1,r;l<=n;l=r+1){
R[++tot]=r=n/(n/l);
g[tot]=((R[tot]+1)/2-1)%mod;
if(R[tot]<=block) id1[R[tot]]=tot;
else id2[n/R[tot]]=tot;
}
for(int j=2;j<=cnt;++j){
for(int i=tot;pri[j]*pri[j]<=R[i];--i){
int pos=getid(R[i]/pri[j]);
ckdel(g[i],del(g[pos],j-2));
}
}
if(pin==-1) pin=add(g[getid(n)],1);
rep(i,1,tot) ckmul(g[i],basnum);
return S(NN,1);
}
}
using Min_25::solve;
signed main(){
freopen("yyds.in","r",stdin); freopen("yyds.out","w",stdout);
n=read();
int tmp=solve(n,(mod+1)/2),val=ksm(2,pin);
int ans1=mul(val,del(((n+1)/2-1)%mod,tmp));
ckmul(val,(mod+1)>>1);
int ans2=mul(val,add(1,solve(n/2,(mod+1)/2)));
print(add(ans1,ans2));
return 0;
}