2020杭电暑期多校第一场
1005.Fibonacci-Sum
标签：二次剩余、二项式展开
已知斐波那契数列通项公式$Fn=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$
把常数用字母代替就是$F_n=d[a^n-b^n]$
然后把要求的每一项二项式展成k+1项$(F_{nc})^K=C_n^0(-1)^na^0b^n+C_n^1(-1)^na^1b^{n-1}+…+C_n^n(-1)^0a^nb^0$把展开后二项式系数相同的项合并起来求和，就是一个等比数列求和的问题。
重点在于如何在模意义下表示根号，比如要表示模意义下的$\sqrt{5}$
那也就是解$x^2=5(mod 1e9+9)$ 当然前提是5是1e9+9的二次剩余，这一部分是二次剩余的内容。
但从做题来说其实可以暴力求x，然后直接把x作为常数引入。求出x之后d就是x的逆元，a和b也能用x表示出来了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+9,N=1e5+5;
int qpower(int x,ll p)
{
int ret=1;
for (int base=x;p;base=(1ll*base*base)%MOD,p=p>>1)
if (p&1) ret=(1ll*ret*base)%MOD;
return ret;
}
int T,k;
ll n,c;
int inv[N];
int mul(ll x,ll y) {
x%=MOD,y%=MOD;
return (1ll*x*y)%MOD;
}
int main()
{
cin>>T;
for (int i=1;i<=100001;i++) inv[i]=qpower(i,MOD-2);
int d=qpower(383008016,MOD-2);//1/sqrt(5)
int A=((1ll*1+383008016)*inv[2])%MOD;//(1+sqrt(5))/2
int B=((1ll*1-383008016+MOD)*inv[2])%MOD;//(1-sqrt(5))/2
while(T--)
{
cin>>n>>c>>k;
int AA=qpower(A,c);
int BB=qpower(B,c);
int invAA=qpower(AA,MOD-2);
int invBB=qpower(BB,MOD-2);
int com=1;
int q=qpower(AA,k);
int QQ=qpower(q,n);
int change=qpower(mul(BB,invAA),n);
int a1=q;
int sum=0;
for (int i=0;i<=k;i++)
{
int tmp;
if (q!=1) tmp=mul(a1,mul((QQ-1+MOD)%MOD,qpower((q-1+MOD)%MOD,MOD-2)));
else tmp=mul(n,a1);
int tt=mul(com,tmp);
if (i%2==1) tt=MOD-tt;
sum=(1ll*sum+tt)%MOD;
QQ=(1ll*QQ*change)%MOD;
a1=mul(mul(a1,BB),invAA);
q=mul(mul(q,BB),invAA);
if (i!=k) com=mul(mul(com,k-i),inv[i+1]);
}
printf("%d\n",mul(sum,qpower(d,k)));
}
return 0;
}
1009.Leading-Robots
标签：单调栈
按机器人位置从大到小排序后维护一个单调栈，存放当前可能成为第一名的机器人。记录机器人成为第一名的时间，如果当前机器人与栈顶机器人相遇的时间比栈顶机器人成为第一名的时间早，说明栈顶在成为第一名之前就被超越了，则将栈顶弹出。由于$s=\frac{1}{2}at^2$，所以可以通过比较$\frac{\Delta s}{\Delta a}$来比较时间。最终还留在栈中的元素数量就是答案。
每个机器人最多进栈出栈一次，所以复杂度为O(n)。
需要特别处理位置和加速度都相同的情况，但不能直接删去。比较好的做法是先用一个tag数组标记一下，然后最后统计答案是检查是否有tag，若有tag则不计入答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,INF=0x3f3f3f3f;
const double eps=1e-4;
int T,n,m,x,y;
struct Robot{
int p, a;
}A[N];
struct status{
double t;
int a, p, id;
};
bool tag[N];
vector<status>st;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for (int i=1;i<=n;i++) scanf("%d %d",&A[i].p,&A[i].a);
sort(A+1,A+1+n,[](Robot x,Robot y){
if (x.p!=y.p) return x.p>y.p;
else return x.a>y.a;
});
memset(tag,0,sizeof(tag));
for (int i=1;i<=n-1;i++)
{
if (A[i].a==A[i+1].a && A[i].p==A[i+1].p) tag[i]=tag[i+1]=1;
}
st.clear();
st.push_back({0,A[1].a,A[1].p,1});
for (int i=2;i<=n;i++)
{
status now=st.back();
if (A[i].a<=now.a) continue;
double t=1.0*(now.p-A[i].p)/(A[i].a-now.a);
while (fabs(t-now.t)<eps || t<now.t)
{
st.pop_back();
now=st.back();
t=1.0*(now.p-A[i].p)/(A[i].a-now.a);
}
st.push_back({t,A[i].a,A[i].p,i});
}
int ans=0;
for (auto x:st) if (!tag[x.id]) ans++;
printf("%d\n",ans);
}
return 0;
}
1006.Finding-a-MEX
标签：分块，树状数组求MEX
根据题意可以很快想到两种解决方法
- 单点修改+询问时遍历所有邻点
- 修改时修改邻点的树状数组+询问时查询树状数组
两种做法都有很明显的缺陷，第一种如果反复询问某个大结点（邻点非常多），第二种如果反复修改大结点，都肯定会T
于是比较巧妙的通过分块来稳定时间复杂度。首先定义度数大于某个临界值的为超级点，（可以取$\sqrt{2m}=450$），其他为小结点（可知超级点个数不超过450）。
每次修改时，单点修改+修改相邻超级点的树状数组。
每次查询时，若该点为超级点，直接通过树状数组查询MEX，若该店为小结点，遍历邻点即可。
在树状数组记录MEX时，对于同一个数只需要记录一次，可以在树状数组的基础上再开一个桶数组，记录某个数出现的次数，只有当出现次数由0变为1或由1变为0时，才对树状数组产生修改。
通过对树状数组二分的方式求MEX。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct BIT{
int SZ;
vector<int>tr;
vector<int>t;
int lowbit(int x){ return x&(-x); }
void init(){
tr.resize(SZ);
t.resize(SZ);
}
void add(int x,int v){
if (x<SZ)
{
t[x]+=v;
if (t[x]==1 && v==1|| t[x]==0 && v==-1)
while(x<SZ)
{
tr[x]+=v;
x+=lowbit(x);
}
}
}
int sum(int x){
int sum=0;
while(x>0)
{
sum+=tr[x];
x-=lowbit(x);
}
return sum;
}
int MEX(){
int l=1,r=SZ-1;
while(l<r)
{
int mid=(l+r)>>1;
if (sum(mid)<mid)
r=mid;
else l=mid+1;
}
return l;
}
}bit[N];
int T,n,m,u,v,x,op,q;
vector<int>G[N];
vector<int>Super[N];
int A[N];
int deg[N];
void init()
{
for (int i=1;i<=n;i++)
{
G[i].clear();
Super[i].clear();
deg[i]=0;
bit[i].tr.clear();
bit[i].t.clear();
bit[i].SZ=0;
}
}
int main()
{
//freopen("finding-a-mex.in","r",stdin);
//freopen("finding-a-mex.out","w",stdout);
cin>>T;
while(T--)
{
cin>>n>>m;
init();
for (int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
A[i]++;
}
for (int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
deg[u]++,deg[v]++;
}
for (int i=1;i<=n;i++)
{
if (deg[i]>=1){
bit[i].SZ=deg[i]+3;
bit[i].init();
}
}
for (int i=1;i<=n;i++)
{
for (int to:G[i])
{
if (deg[to]>=1)
{
Super[i].push_back(to);
bit[to].add(A[i],1);
}
}
}
cin>>q;
while(q--)
{
scanf("%d",&op);
if (op==1)
{
scanf("%d%d",&u,&x);
x++;
for (auto to:Super[u])
{
bit[to].add(A[u],-1);
bit[to].add(x,1);
}
A[u]=x;
}
else
{
scanf("%d",&x);
int ans=1;
if (deg[x]>=1)
ans=bit[x].MEX();
else
{
vector<int>now;
for (auto to:G[x])
{
now.push_back(A[to]);
}
sort(now.begin(),now.end());
for (auto p:now)
{
if (p>ans) break;
ans=p+1;
}
}
printf("%d\n",ans-1);
}
}
}
return 0;
}