2023.5.18测试
T1 金币
（其实是原题 P3951 [NOIP2017 提高组] 小凯的疑惑）
给定 \(a,b\in \mathrm{N^*}\)，求最大的不能表示成 \(ax+by\:\:(x,y\in \mathrm{N})\) 的数字
考场上想了很久，幸好搞出来了
因为 \(\gcd(a,b)=1\)，所以如果 \(x,y\in\mathrm{Z}\)，那么由 \(\mathrm{B\acute{e}zout}\) 定理知 \(ax+by\) 可以表示出任意的整数。
但现在 \(x,y\) 有自然数的限制，所以当 \(x\) 或 \(y\) 小于 \(0\) 时式子表示出来的数不一定能够用两个大于等于 \(0\) 的 \(x,y\) 表示出来。那我们就考虑 \(x,y\) 取到多少表示出来的数一定是不合法的，且让这个数最大
考虑让 \(x>0,y<0\)。容易发现，当 \(x\geq b\) 时，可以将式子变形成 \(a(x-b)+b(y+a)\)，也就是说 \(x\) 大于等于 \(b\) 的部分可以抵消到后面 \(y\) 的负值，那此时 \(y+a\) 可能就可以大于等于 \(0\)，那这个式子表示出来的数就是合法的。就算此时 \(y+a\) 仍然小于 \(0\)，那它肯定也是不比\(y=-1\) 更优的。所以直接让 \(x=b-1,y=-1\) 即可
综上，答案为 \(a(b-1)+b\times(-1)=ab-a-b\)
T2 字符串计数
一个长度为 \(len\) 的字符串，包括至少 \(a\) 个大写字母，\(b\) 个小写字母，\(c\) 个数字，求有多少个符合条件的字符串。答案模 \(10^9+9\)。
考场上脑瘫把组合写成排列了，一直搞不出来，最后喜提 \(15\) 分
设大写字母、小写字母，数字的数量依次为 \(i,j,k\:(i+j+k=len)\)，那么此时对答案的贡献为 \(26^i\times26^j\times10^k\times \binom{i+j}{i}\times\binom{len}{i+j}\)
考虑 \(O(n^2)\) 枚举 \(i,j\)，可以拿到 \(36\) 分
现在思考如何优化。观察到大小写字母的底数都是 \(26\)，所以考虑把它们合并在一起。设 \(f(n)\) 表示大小写字母共选了 \(n\) 个的方案数 \((a+b\leq n\leq len-k)\)，那么最终答案就为 \(\sum\limits_{i=1}^{len-k}{f(i)\times10^{len-i}\times\binom{len}{len-i}}\)
考虑如何计算 \(f(n)\)：
设 \(g(n)=\sum\limits_{i=a}^{n-b}{\binom{n}{i}}\)，因为 \(n\geq a+b\)，所以第一项为 \(g(a+b)=\binom{a+b}{a}\)。考虑递推式子，将 \(g(n)\) 放到杨辉三角上可看出：
可 \(O(n\log MOD)\) 递推出来
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=200010;
const LL MOD=1e9+9;
int len,a,b,c;
LL fac[N],f[N],g[N],ans;
LL ksm(LL x,LL y)
{
if(y==0)
return 1;
if(y==1)
return x;
LL tmp=ksm(x,y/2);
if(y&1)
return tmp*tmp%MOD*x%MOD;
return tmp*tmp%MOD;
}
LL C(int a,int b)
{
if(a<b || a<0 || b<0)
return 0;
if(b==0)
return 1;
if(a==0)
return 0;
return fac[a]*ksm(fac[a-b],MOD-2)%MOD*ksm(fac[b],MOD-2)%MOD;
}
int main()
{
fac[0]=1;
for(int i=1; i<=2e5+1; i++)
fac[i]=(fac[i-1]*i)%MOD;
scanf("%d%d%d%d",&len,&a,&b,&c);
if(a+b+c>len)
{
printf("0");
return 0;
}
for(int i=a+b; i<=len-c; i++)
{
if(i==a+b) //注意这地方当a+b=0时就不好递推了，所以边界自己处理
g[i]=C(i,a);
else
g[i]=(g[i-1]*2%MOD+C(i-1,a-1)+C(i-1,i-b))%MOD;
f[i]=ksm(26,i)*g[i]%MOD;
(ans+=f[i]*ksm(10,len-i)%MOD*C(len,len-i)%MOD)%=MOD;
}
printf("%lld",ans);
return 0;
}
T3 树
一棵带边权的树，边权为 \([0,9]\) 内的整数。问有多少点对 \((u,v)\)，满足将 \(u\rightarrow v\) 简单路径上的边权串成一个整数 \(x\)，\(x\) 是 \(m\) 的倍数。
\(2\leq n\leq 10^5\)，\(1\leq m\leq 10^9\) 且 \(m\perp 10\)
一眼点分治。考场上迅速码完，calc 函数直接两重循环暴力判断。由于数据太弱，喜提 \(100\)
不过还是要思考如何优化
对于 \((u,v)\) 来说，设 \(a\) 为 \(u\rightarrow rt\) 路径上串成的数，\(b\) 为 \(rt\rightarrow v\) 路径上串成的数，\(dep\) 为 \(v\) 的深度。则
利用 \(m\perp 10\) 除以 \(10^{dep}\)
把 \(a,\dfrac{b}{10^{dep}}\) 分别丢进两个不同的 \(\mathrm{map}\) 即可
对于 \((v,u)\) 来说，情况类似
预处理出 \(10\) 的正整数次幂的逆元，时间复杂度 \(O(n\log^2 n)\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100010,M=5000010;
struct node
{
LL sa,sb; //sa倒着，sb正着
int cnt;
}a[N];
int n,p,L;
int rt,rt_size,size[N];
int head[N],nxt[2*N],ver[2*N],edge[2*N],tot;
bool v[N];
LL m,inv[N],ans;
map <LL,int> aa,bb;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1; y=0;
return a;
}
LL d=exgcd(b,a%b,x,y);
LL tmp=x;
x=y; y=tmp-(a/b)*y;
return d;
}
void add(int x,int y,int z)
{
ver[++tot]=y; edge[tot]=z;
nxt[tot]=head[x]; head[x]=tot;
}
void find_root(int x,int fa,int Large)
{
int max_part=0;
size[x]=1;
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i];
if(y==fa || v[y])
continue;
find_root(y,x,Large);
size[x]+=size[y];
max_part=max(max_part,size[y]);
}
max_part=max(max_part,Large-size[x]);
if(max_part<rt_size)
{
rt=x;
rt_size=max_part;
}
}
void dfs(int x,int fa,LL numa,LL numb,LL pw,int t)
{
a[++p]=(node){numa,numb*inv[t]%m,t};
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i],z=edge[i];
if(y==fa || v[y])
continue;
LL nta=(1LL*z*pw+numa)%m;
LL ntb=(numb*10%m+(LL)z)%m;
dfs(y,x,nta,ntb,pw*10%m,t+1);
}
}
void calc()
{
for(int i=1; i<=p; i++)
{
ans+=(LL)bb[(m-a[i].sa)%m];
ans+=(LL)aa[(m-a[i].sb)%m];
}
for(int i=1; i<=p; i++)
{
aa[a[i].sa]++;
bb[a[i].sb]++;
}
p=0;
}
void solve(int x,int fa,int Large)
{
rt_size=Large+1;
find_root(x,fa,Large);
v[rt]=1;
p=0;
aa[0]++; bb[0]++;
for(int i=head[rt]; i; i=nxt[i])
{
int y=ver[i],z=edge[i];
if(y==fa || v[y])
continue;
dfs(y,rt,(LL)z%m,(LL)z%m,10,1);
calc();
}
aa.clear(); bb.clear();
for(int i=head[rt]; i; i=nxt[i])
{
int y=ver[i];
if(y==fa || v[y])
continue;
solve(y,x,size[y]);
}
}
int main()
{
scanf("%d%lld",&n,&m);
for(int i=1; i<n; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++; y++;
add(x,y,z); add(y,x,z);
}
LL pw=1;
for(int i=1; i<=n; i++)
{
(pw*=10)%=m;
LL x,y;
exgcd(pw,m,x,y);
x=(x%m+m)%m;
inv[i]=x;
}
solve(1,0,n);
printf("%lld",ans);
return 0;
}
\(100+15+100=215\)，\(\mathrm{rk}\space6\)