2020杭电暑假多校第一场

第五题： Fibonacci Sum

我们写出斐波那契的通项公式，然后令a=1+sqrt(5)/2, b=1-sqrt(5)/2，因为5是1e9+9的二次剩余。用x来替代，那么我们a就可以变成(1+x)*inv2，同理b变成(1-x)*inv2。写出替换之后我们二项式展开然后就可以发现当我们r和c固定的时候，C后面就是一串等比数列，所以用等比数列求和公式和欧拉降幂就可以得到答案了。

#include<bits/stdc++.h>
//#define int long long
typedef long long ll;
using namespace std;
const int N=1e5+10,inv2=500000005,p=383008016,mod=1e9+9;
const int a=691504013;
const int b=308495997;
ll n,c,k,inv[N],f[N],mia[N],mib[N];
inline ll qmi(ll a,ll b){
    ll ret=1;
    for (;b;b>>=1,a=a*a%mod)
        if (b&1)
            ret=ret*a%mod;
    return (ret+mod)%mod;
}

inline ll C(int n,int m) {
    return f[n]*inv[m]%mod*inv[n-m]%mod;
}
ll ph(ll x){
    ll res=x,a=x;
    for(ll i=2;i*i<=x;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}
inline ll Inv(ll x){
    return qmi(x,mod-2);
}
inline void solve(){
    scanf("%lld%lld%lld",&n,&c,&k);
    ll Ans=0;
    ll pp=ph(mod);
    for (int j=0;j<=k;j++){
        ll t=mia[k-j]*mib[j]%mod,tem;
        t=qmi(t,c%pp);
        tem=t==1?n%mod:t*(qmi(t,n%pp)-1+mod)%mod*Inv(t-1)%mod;
        if (~j&1)
            Ans+=C(k,j)*tem%mod,Ans%=mod;
        else
            Ans+=mod-C(k,j)*tem%mod,Ans%=mod;
    }
    Ans=Ans*qmi(276601605LL,k)%mod;
    printf("%lld\n",Ans);
}
void get(int n) {
    f[0]=1; for (int i=1;i<=n;i++) f[i]=f[i-1]*i%mod;
    inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    inv[0]=1; for (int i=1;i<=n;i++) inv[i]=inv[i]*inv[i-1]%mod;
    mia[0]=mib[0]=1;
    for(int i=1;i<=n;i++) mia[i]=mia[i-1]*a%mod,mib[i]=mib[i-1]*b%mod;
}
signed main() {
    get(1e5);
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

第八题：Leading Robots

题解：
首先我们把数组按照加速度从小到大，起点从小到大排序。然后维护一个栈内元素依次当第一的所有情况。首先我们排序完了之后后面的加速度一定大于前面，所以一定会存在某个时刻后面超过前面，所以如果前面的起点都在后面的起点之后的话那么前面的元素就不可能当过第一，所以就直接弹掉。否则我们画图可以发现，t2需要大于t1，否则第三辆车会在第二辆车之前超过第一。最后我们之前统计加速度和起点相同的点，如果单调栈维护了这么一个点那么答案就减减。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pp;
vector<pp> g,res;
const int N=50000+10;
int st[N];
int cmp(pp a,pp b){
    if(a.second==b.second) return a.first<b.first;
    return a.second<b.second;
}
int fun(pp a,pp b,pp c){
    return (b.first-c.first)*(b.second-a.second)-(a.first-b.first)*(c.second-b.second)<=0;
}
signed main()
{
    int t; scanf("%lld",&t);
    while(t--){
        int cnt=0;
        int n; scanf("%lld",&n);
        g.clear();
        map<pp,int> ma;
        for(int i=0;i<n;i++) {
            pp tmp;
            scanf("%lld%lld",&tmp.first,&tmp.second);
            g.push_back(tmp);
            ma[tmp]++;
        }
        sort(g.begin(),g.end(),cmp);
        st[++cnt]=0;
        for(int i=1;i<n;i++) {
            while(((cnt>0&&g[st[cnt]].first<=g[i].first)||(cnt>1&&fun(g[st[cnt-1]],g[st[cnt]],g[i])))) cnt--;
            st[++cnt]=i;
        }
        int res=cnt;
        for(int i=1;i<=cnt;i++){
            if(ma[g[st[i]]]>1) res--;
        }
        printf("%lld\n",res);
    }
}