模拟赛
\(long\ long\ ago\)。。。
T1 Company Acquisitions
鞅的停时定理。
赛时应该不可做的吧。
手膜两组样例发现肯定不能用常规方法做。然后开始新科技。
势能函数！！！
设计一个势能函数去表示一种状态，这个势能函数要满足每操作一步势能减一，这样初势能减末势能就是期望步数。
（是不是直接把势能差看成期望步数就行？）
对于本道题来说，设 \(f(x)\) 表示有 \(x\) 个儿子的点的势能，所以某一状态的势能就是 \(\sum f(x)\)，末势能为 \(f(n-1)\)。
我们想要找出势能函数之间的递推关系，对于任意两个点，显然有以下式子：
\[f(x)+f(y)-1=\frac{f(x+1)+yf(0)+f(y+1)+xf(0)}{2} \]对 \(f(0)\)，我们根本不在乎它的取值，因为最终求得是势能差，所以不妨设 \(f(0)=0\)。
由于 \(f(x)\) 与 \(f(x+1)\)、\(f(y)\) 与 \(f(y+1)\) 之间一定有相同的递推关系，所以：
\[f(x)-\frac{1}{2}=\frac{1}{2}f(x+1) \]转化成等比数列的形式（注意是负数）：
\[f(n)=1-2^n; \]然后就很简单啦！（所以鞅的停时定理是啥？）（好像真的是板子题）
附赠小饼干 Slime and Biscuits + 快踩
code
```cpp #includeT2 数学作业
又是矩阵加速板子。。。
突破点在递推关系，每加一个数 \(x\) 就是原数乘以 \(10^{len_x}\) 再加原数。
因此我们可以用 dp 的方法解决。而数据范围暗示了矩阵加速。
因为位数是不定的，所以考虑按数字长度分段进行操作。复杂度带一个 \(log_{10}\)。
注意 __int128。
code
#include<bits/stdc++.h>
using namespace std;
#define LL __int128
long long n,m;
struct M
{
LL x,y,mat[4][4]={};
M operator * (const M &a) const
{
M c; c.x=x; c.y=a.y;
for(int i=1;i<=x;i++)
for(int j=1;j<=a.y;j++)
for(int k=1;k<=y;k++)
c.mat[i][j]=(c.mat[i][j]+mat[i][k]*a.mat[k][j]%m)%m;
return c;
}
};
M qpow(M a,M b,LL c)
{
while(c)
{
if(c&1) a=(a*b);
b=(b*b); c>>=1;
}
return a;
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%lld%lld",&n,&m);
M a,b;
a.x=1; a.y=b.x=b.y=3;
a.mat[1][2]=a.mat[1][3]=1;
b.mat[2][1]=b.mat[2][2]=b.mat[3][2]=b.mat[3][3]=1;
for(LL i=1,j=1;;i++)
{
j=b.mat[1][1]=j*10;//注意 j 不要 mod
b.mat[1][1]%=m;
if(n<j)
{
a=qpow(a,b,n-j/10+1);
break;
}
a=qpow(a,b,j-j/10);
}
printf("%lld\n",(long long)a.mat[1][1]);
return 0;
}
T3 「P6156 简单题」加强版
开始莫反。。。
求： $$ \sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\gcd(i,j)) \pmod {2^{32}} $$ 套路： $$ \begin{aligned} ans&=\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\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\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}(id+jd)^k[gcd(i,j)=1]\\ &=\sum_{d=1}^{n}\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}(i+j)^k[gcd(i,j)=1]\\ &=\sum_{d=1}^{n}\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}(i+j)^k\sum_{e\mid gcd(i,j)}^{n}\mu(e)\\ &=\sum_{d=1}^{n}\mu^2(d)d^{k+1}\sum_{e=1}^{\lfloor \frac{n}{d} \rfloor}\mu(e)e^k \sum_{i=1}^{\lfloor \frac{n}{de} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{de} \rfloor}(i+j)^k\\ &=\sum_{d=1}^{n}\sum_{e=1}^{\lfloor \frac{n}{d} \rfloor}d^{k+1}e^k\mu^2(d)\mu(e)\sum_{i=1}^{\lfloor \frac{n}{de} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{de} \rfloor}(i+j)^k \end{aligned} $$ $$ S(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^k $$ $$ T=de $$ $$ \begin{aligned} ans&=\sum_{d=1}^{n}\sum_{e=1}^{\lfloor \frac{n}{d} \rfloor}d^{k+1}e^k\mu^2(d)\mu(e)S(\lfloor \frac{n}{de} \rfloor)\\ &=\sum_{T=1}^{n}T^k S(\lfloor \frac{n}{T} \rfloor)\sum_{d \mid T}\mu^2(d)\mu(\frac{n}{d})d \end{aligned} $$ 先考虑筛 $S(n)$，令 \(F(x)=\sum_{i=1}^{x}i^k\)，\(G(x)=\sum_{i=1}^{x}F(i)\)。
则 \(S(n)=G(2n)-2G(n)\)。（数学归纳法可证，直接感性理解更好？）
两次前缀和就可以了。
然后考虑筛 \(\sum_{d \mid T}\mu^2(d)\mu(\frac{n}{d})d\)。
再考虑 \(f(n) = \sum_{d|n}d \mu^2(d)\mu(\frac{n}{d})\)：由于是一堆积性函数的狄利克雷卷积的形式，则 \(f(n)\) 也一定是积性函数。
考虑欧拉筛筛中 \(x\) 时，枚举到的质因数是 \(p\)。从 \(\mu\) 函数着手考虑，则讨论 \(p\) 在 \(x\) 中的最高次幂因子：假设 \(p^k \mid x\) 且有 \(p^{k+1} \nmid x\)：
根据积性函数性质，则有：\(f(x) = f(p^k) \times f(\frac{x}{p^k})\)。
讨论一下 \(f(p^k)\) 的取值：
- \(k=0\)，即 \(f(1)\) 的取值一定为 \(1\)。
- \(k=1\)，则 \(f(p) = 1 \mu^2(1) \mu(p) + p \mu^2(p) \mu(1) = p-1\)。
- \(k=2\)，则 \(f(p^2) = 1 \mu^2(1) \mu(p^2) + p \mu^2(p) \mu(p) + p^2 \mu^2(p^2) \mu(1)=-p\)。
- \(k \ge 3\)，由于鸽笼原理，此时 \(d\) 和 \(\frac{x}{d}\) 中至少有一个能被 \(p^2\) 整除，则那一个的 \(\mu\) 的值为 \(0\)。所以此时 \(f(p^k)=0\)。
（借鉴一下）
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7+5;
#define LL unsigned int
LL p[N],f[N],F[N],n,k,t;
bool vs[N];
inline LL qpow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=res*a;
a=a*a; b>>=1;
}
return res;
}
inline void init()
{
f[1]=F[1]=1;
for(int i=2;i<=n<<1;i++)
{
if(!vs[i]) f[i]=i-1,F[i]=qpow(i,k),p[++p[0]]=i;
for(int j=1;j<=p[0]&&i*p[j]<=n<<1;j++)
{
vs[p[j]*i]=1; F[i*p[j]]=F[i]*F[p[j]];
if(i%p[j]==0)
{
if((i/p[j])%p[j]) f[i*p[j]]=(-p[j])*f[i/p[j]];
break;
}
f[p[j]*i]=f[i]*(p[j]-1);
}
}
for(int i=2;i<=n<<1;i++) f[i]=(f[i-1]+f[i]*F[i]),F[i]=(F[i-1]+F[i]);
for(int i=2;i<=n<<1;i++) F[i]=(F[i-1]+F[i]);
}
inline LL cal(LL x)
{
return ((F[x<<1]-(F[x]<<1)));
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("o1.out","w",stdout);
scanf("%u%u%u",&t,&n,&k);
init();
while(t--)
{
scanf("%u",&n);
LL ans=0;
for(int l=1,r;l<=n;l=r+1)
{
r=(n/(n/l));
ans=(ans+((f[r]-f[l-1]))*cal(n/l));
}
printf("%u\n",ans);
}
return 0;
}
T4
图
水题放 T4。。。
没啥，直接数位 dp 相当好写（其实没有 dp），其实直接贪也行吧。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
#define LL long long
LL n;
int len,ans,a[N];
int dfs(int p,int sum,bool c)
{
if(!p) return sum;
if(!c) return sum+9*p;
int res=0;
res=max(dfs(p-1,sum+a[p],1),a[p]-1>=0?dfs(p-1,sum+a[p]-1,0):0);
return res;
}
int work(LL x)
{
len=0; while(x) a[++len]=x%10,x/=10;
return dfs(len,0,1);
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%lld",&n);
printf("%d\n",work(n));
return 0;
}