暑假集训CSP提高模拟10
组题人： @worldvanquisher
\(T1\) P170. 黑暗型高松灯 \(0pts\)
- 原题： CF1025G Company Acquisitions
- 科技题目，直接贺官方题解了。
考虑势能函数。如果我们使得每操作一步期望势能 \(-1\)，那么初势能减末势能就是答案。
设一个点有 \(x\) 个儿子的势能为 \(f(x)\)，那么考虑现在选中两个儿子个数为 \(x,y\) 的：
\[\frac 12(f(x+1)+yf(0))+\frac 12(f(y+1)+xf(0))-f(x)-f(y)=-1 \]不妨令 \(f(0)=0\) （其实好像是随意定的），那么同构一下得到 \(f(x)=1-2^x\)，初减末即可。
其实是有应用条件的，但是大多数时候是你觉得能用就能用。详见 https://www.cnblogs.com/C202044zxy/p/16340757.html 第一道例题
部分分尊重原题。
\(T2\) P168. 速度型高松灯 \(95pts\)
-
设 \(F_{n}=\begin{bmatrix} n & f_{n} & 1 \end{bmatrix}\) ，容易有 \(\begin{aligned} F_{n} &= F_{10^{k-1}-1} \times \begin{bmatrix} 1 & 1 & 0 \\ 0 & 10^{k} & 0 \\ 1 & 1 & 1 \end{bmatrix}^{n-(10^{k-1}-1)} \end{aligned}\) ，其中 \(n \in [10^{k-1},10^{k})\) 。
-
因为 \(k \in [0, \left\lfloor \log_{10}n \right\rfloor+2]\) ，每个 \(k\) 单独算就行了。
点击查看代码
#define ll __int128_t struct Matrix { ll ma[5][5]; Matrix() { memset(ma,0,sizeof(ma)); } }f,a; Matrix mul(Matrix a,Matrix b,ll n,ll m,ll k,ll p) { Matrix c; for(ll i=1;i<=n;i++) { for(ll j=1;j<=k;j++) { for(ll h=1;h<=m;h++) { c.ma[i][j]=(c.ma[i][j]+a.ma[i][h]*b.ma[h][j]%p)%p; } } } return c; } Matrix qpow(Matrix a,ll b,ll p,ll n) { Matrix ans; for(ll i=1;i<=n;i++) { ans.ma[i][i]=1; } while(b) { if(b&1) { ans=mul(ans,a,n,n,n,p); } b>>=1; a=mul(a,a,n,n,n,p); } return ans; } int main() { ll b,p,n=1,m=3,k=3,i; scanf("%lld%lld",&b,&p); f.ma[1][3]=1; for(i=10;i/10<=b;i*=10) { a.ma[1][1]=a.ma[1][2]=a.ma[3][1]=a.ma[3][2]=a.ma[3][3]=1; a.ma[2][2]=i%p; f=mul(f,qpow(a,min(i,b+1)-i/10,p,m),n,m,k,p); } printf("%lld\n",f.ma[1][2]); return 0; }
\(T3\) P169. 力量型高松灯 \(0pts\)
- 部分分
- \(20pts\) ：暴力枚举即可，时间复杂度为 \(O(n^{2} \log n+n \log k)\) ，可以使用扩展欧拉定理优化，使时间复杂度为 \(O(n^{2} \log^{2}n +n \log \sqrt{p})\) 。
- 正解
- 没学莫反，先贺官方题解了。
一开始这题非常水，搬题人觉得太水了想让大家稍微动动脑子。反正有两个水题一个不可做，多玩玩式子也挺好的。
不过其实也挺水的。赛时有老哥 \(O(n^{\frac 34})\) 拿了 90 分。其实挂个多测就卡掉了，但是不想卡。
不是哥们你 90 分怎么又 MLE 爆零了
\[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j)\\ =&\sum_{d=1}^n\mu^2(d)d\sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d]\\ =&\sum_{d=1}^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k[\gcd(i,j)=1]\\ =&\sum_{d=1}^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k\sum_{e|i,e|j}\mu(e)\\ =&\sum_{e=1}^n\mu(e)e^k\sum_{d=1}^{\lfloor\frac ne\rfloor}\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac n{de}\rfloor}\sum_{j=1}^{\lfloor\frac n{de}\rfloor}(i+j)^k\\ =&\sum_{T=1}^nS\left(\left\lfloor\frac nT\right\rfloor\right)T^k\sum_{d|T}\mu^2(d)\mu\left(\frac Td\right)d \end{aligned} \]其中 \(S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\)。
两个问题：\(S(n)\) 怎么算，后边怎么筛。
后边怎么筛其实是个更简单的问题。设他是 \(f(n)\)。手玩一下可以发现对于 \(n\) 的一个质因子 \(p\)，如果 \(p\) 的次数 \(\ge 3\) 那么 \(f(n)=0\)。这是显然的。于是可以直接筛到的时候算一下质因子的次数暴力算。
前边 \(S(n)\)。观察一下这玩意的贡献其实是：设 \(F(n)=\sum_{i=1}^ni^k,G(n)=\sum_{i=1}^nF(i)\)，那么 \(S(n)=G(2n)-2G(n)\)。线筛一下 \(i^k\)，做完了。
没事的可以试试后边这个函数怎么亚线性筛。
\(T4\) P167. 高松灯 \(100pts\)
-
数位 \(DP\) 板子。
点击查看代码
ll a[25],f[25][180],sum=0; ll divide(ll n,ll a[]) { ll len=0; while(n) { len++; a[len]=n%10; n/=10; } return len; } ll dfs(ll pos,ll pre,ll lead,ll limit) { if(pos<=0) { return pre; } if(f[pos][pre]!=-1&&lead==0&&limit==0) { return f[pos][pre]; } ll ans=0,maxx=(limit==0)?9:a[pos],i; for(i=0;i<=maxx;i++) { ans=max(ans,dfs(pos-1,pre+i,(i==0)*lead,(i==maxx)*limit)); } return (lead==0&&limit==0)?f[pos][pre]=ans:ans; } ll ask(ll n) { ll len=divide(n,a); return dfs(len,0,1,1); } int main() { ll n; cin>>n; memset(f,-1,sizeof(f)); cout<<ask(n)<<endl; return 0; } -
最终答案只会来自两种情况，一种是原数，一种是首位放 \(1\) 其余全是 \(9\) ，二者取 \(\max\) 即可。
总结
- 赛时历程：先溜了一眼题， \(T1\) 直接弃掉， \(T2\) 之前做过但细节有点多， \(T3\) 可以骗点分， \(T4\) 之前做过类似的且几乎是数位 \(DP\) 纯板子。遂先写 \(T4\) ，因为太过着急导致少打了个负号，少搜了许多状态，花 \(20 \min\) 才调出来；然后写 \(T2\) ，式子因为之前写的时候有点麻烦，遂写了个简单点的，但还是在调细节，调了 \(1h\) ;接着是 \(T3\) ，推到最后发现漏了一个 \(\gcd(i,j)=1\) 导致预处理直接死掉，交了个暴力上去； \(T1\) 特判了两种情况。
- \(T2\) 枚举 \(10^{k}\) 时炸
long long了，挂了 \(5pts\) 。 - \(T3\) 暴力预处理 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1] \times (i+j)^{k}\) 时空间开大了，再次 \(MLE\) ，挂了 \(20pts\) 。
后记
-
难度不单调递增。
-
因赛时能过 \(T1\) 太过逆天，所以奖励也很逆天。
