T1 排队打水
小学级别的贪心题
T2 Oversleeping
一道不错的扩欧题，一开始没反应过来，一直搞不等式……
根据题意可以知道在 \(B\) 站停留的时间区间为 \([k(2n+2m)+n,k(2n+2m)+n+m)\quad(k\in \mathbb{Z})\)
清醒的时间区间为 \([k'(p+q)+p,k'(p+q)+p+q)\quad(k'\in \mathbb{Z})\)
由于 \(m,q\) 的范围小，所以我们可以枚举 \(i\in[0,m),j\in[0,q)\)，那么接下来我们只需令 \(k(2n+2m)+n+i=k'(p+q)+p+j\)，移项一下得：
\[(2n+2m)k-(p+q)k'=p+j-n-i \]扩欧求解即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int T;
LL p,q,n,m;
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;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&n,&m,&p,&q);
LL a,b,c,d,x,y,ans=(2*n+2*m)*(p+q)+1;
a=2*n+2*m;
b=p+q;
for(int i=0; i<m; i++)
{
for(int j=0; j<q; j++)
{
c=p-n+j-i;
d=exgcd(a,b,x,y);
if(c%d)
continue;
x=x*c/d;
x=(x%(b/d)+(b/d))%(b/d);
ans=min(ans,x*(2*n+2*m)+n+i);
}
}
if(ans==(2*n+2*m)*(p+q)+1)
printf("infinity\n");
else
printf("%lld\n",ans);
}
return 0;
}
T3 XOR Tree
一道神仙题，膜拜zby大佬赛时AC
学会了：对边权下手一次 \(O(n)\)，不好弄，所以把边权转移成点权
定义一个点的点权为与它相连的所有边的边权异或和，然后我们发现对 \((x,y)\) 这条链上的修改其实只对端点 \(x,y\) 造成影响。而当最终边权为 \(0\)，也就意味着点权为 \(0\)
因此，问题转化成每次任意选 \(2\) 个点进行异或操作，求最终每个点点权为 \(0\) 的最小步数
显然可能有些点权是相同的，那我们贪心地优先将它们异或为 \(0\)，直到每种数字出现的次数至多为 \(1\)
又因为值域最大 \(15\)，所以考虑状压。设 \(f[s]\) 表示集合 \(s\) 异或成 \(0\) 的最小步数。而我们注意到，如果 \(s\) 集合里的数异或和都不为 \(0\)，那不管怎么样都无法达成目的，因为一次操作对总异或和没有影响。又注意到若对于一个合法的集合 \(s\) 最暴力的方法就是两两配对，所以初始化 \(f[s]=|s|-1\)
那么我们枚举集合的每个子集进行转移即可，注意最终答案要加上贪心的操作
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=18;
int n,a[N],ans;
int s,cnt[M],t[1<<M],f[1<<M],sum[1<<M];
int main()
{
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i=1; i<n; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[++x]^=z; a[++y]^=z;
}
for(int i=1; i<=n; i++)
cnt[a[i]]++;
for(int i=1; i<=15; i++)
{
ans+=cnt[i]/2; //贪心
s+=((cnt[i]&1)<<i-1); //记录最终状态s
}
for(int i=1; i<=(1<<15)-1; i++)
t[i]=t[i>>1]+(i&1); //预处理每个状态几个1
for(int i=1; i<=(1<<15)-1; i++)
{
for(int j=1; j<=15; j++) //预处理每个状态的异或和
if(i&(1<<j-1))
sum[i]^=j;
if(!sum[i])
f[i]=t[i]-1;
}
f[0]=0;
for(int i=0; i<=(1<<15)-1; i++)
{
if(sum[i]!=0)
continue;
for(int j=i; j; j=(j-1)&i) //枚举子集
f[i]=min(f[i],f[j]+f[i^j]);
}
printf("%d",ans+f[s]);
return 0;
}
T4 棋子
一个 \(n\) 行 \(m\) 列的棋盘，棋子可以攻击同一行内且距离不超过 \(d\) 的棋子。现在可以在棋盘放任意多个棋子，但任意两个棋子都不能相互攻击。问有多少种不同的方案，答案模 \(100003\)。
\(1\leq n,m,d\leq 10^9\)
一道需要分段来做的题
显然行和行之间无影响，只需计算一行的方案数 \(ans\)，答案即为 \(ans^n-1\)
在考场上主要往组合数方面想，暴力枚举一行放了 \(i\) 个棋子，则可以理解成有 \(i-1\) 个空中间至少有 \(d\) 个格子，将这些格子去掉在剩下的格子就可以随便选 \(i\) 个，所以贡献为
\[\binom{m-(i-1)\times d}{i} \]当时没管数据范围直接交上去拿了 \(40\) 分
注意到模数比较小，其实可以套用 \(\rm Lucas\) 定理，把复杂度优化到 \(O(\frac{m}{d}\log_{100003}{m})\)。当然，这样做的前提是 \(d\) 比较大，如果 \(d\) 很小还这样做显然超时
那 \(d\) 比较小时怎么办呢？
考虑 \(\rm dp\)，设 \(f[i]\) 表示前 \(i\) 个格子放置棋子的方案数，则因为第 \(i\) 个格子可放可不放，所以 \(f[i]=f[i-1]+f[i-d-1]\:\:(i>d)\)。当 \(0\leq i\leq d\) 时，\(f[i]=i+1\)
这显然可以通过矩阵快速幂来进行优化。下面以 \(d=3\) 为例：
构造初始矩阵：
\[\begin{bmatrix}f[3]&f[2]&f[1]&f[0]\end{bmatrix} \]构造转移矩阵：
\[\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\1&0&0&1\end{bmatrix} \]设置分段点为 \(d=200\)，矩阵快速幂的复杂度约为 \(O(\log_2200\times200^3)\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=10000010,M=210;
const int MOD=100003;
int n,m,d;
int fac[N],inv[N];
struct matrix
{
int row,col,data[M][M];
matrix(int r,int c){row=r;col=c;memset(data,0,sizeof(data));}
};
matrix operator * (const matrix &x,const matrix &y)
{
matrix c(x.row,y.col);
for(int i=1; i<=x.row; i++)
for(int j=1; j<=y.col; j++)
for(int k=1; k<=x.col; k++)
(c.data[i][j]+=1LL*x.data[i][k]*y.data[k][j]%MOD)%=MOD;
return c;
}
int ksm(int x,int y)
{
int res=1;
while(y)
{
if(y&1)
res=1LL*res*x%MOD;
x=1LL*x*x%MOD;
y>>=1;
}
return res;
}
void prework()
{
fac[0]=inv[0]=1;
for(int i=1; i<MOD; i++)
{
fac[i]=1LL*fac[i-1]*i%MOD;
inv[i]=ksm(fac[i],MOD-2);
}
}
int C(int a,int b)
{
if(b>a)
return 0;
return 1LL*fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}
int Lucas(int a,int b)
{
if(b>a)
return 0;
if(!a || !b)
return 1;
return 1LL*C(a%MOD,b%MOD)*Lucas(a/MOD,b/MOD)%MOD;
}
int main()
{
prework();
scanf("%d%d%d",&d,&n,&m);
if(d<=200)
{
if(m<=d)
{
printf("%d",(ksm(m+1,n)-1+MOD)%MOD);
return 0;
}
matrix ans(1,d+1);
matrix a(d+1,d+1);
for(int i=1; i<=d+1; i++)
ans.data[1][i]=d+1-i+1;
a.data[1][1]=a.data[d+1][1]=1;
for(int i=2; i<=d+1; i++)
a.data[i-1][i]=1;
m-=d;
for(; m; m>>=1)
{
if(m&1)
ans=ans*a;
a=a*a;
}
printf("%d",(ksm(ans.data[1][1],n)-1+MOD)%MOD);
}
else
{
int ans=0;
for(int i=0; m-d*(i-1)>=i; i++)
(ans+=Lucas(m-d*(i-1),i))%=MOD;
printf("%d",(ksm(ans,n)-1+MOD)%MOD);
}
return 0;
}