板子2

自然数幂和

$\sum_{i=1}^n i^k,1 \le n \le 10^{18},1 \le k \le 50000$
时间$O(klogk).$

const int N=50010;
const int mod=1e9+7;
ll quick_pow(ll base,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}
ll y[N];
ll inv[N];
void init(){
    inv[0]=1;
    for(int i=1;i<N;i++){
        inv[i]=quick_pow(i,mod-2);
    }
}
//0-n
ll l[N],r[N];
ll solve(int n,ll x){
    l[0]=x;
    for(int i=1;i<=n;i++) l[i]=l[i-1]*(x-i)%mod;
    r[n]=x-n;
    for(int i=n-1;i>=0;i--) r[i]=r[i+1]*(x-i)%mod;
    ll ans=0,cur=1;
    for(int i=1;i<=n;i++) (cur*=inv[i])%=mod;
    if(n&1) cur=-cur;
    for(int i=0;i<=n;i++){
        ll t=1;
        if(i>0) (t*=l[i-1])%=mod;
        if(i<n) (t*=r[i+1])%=mod;
        ans+=y[i]*t%mod*cur;
        ans%=mod;
        cur=cur*(-n+i)%mod*inv[i+1]%mod;
    }
    if(ans<0) ans+=mod;
    return ans;
}
ll s(ll n,int k){
    n%=mod;
    if(n<=k+1){
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans+=quick_pow(i,k);
            if(ans>=mod) ans-=mod;
        }
        return ans;
    }
    y[0]=0;
    for(int i=1;i<=k+1;i++){
        y[i]=y[i-1]+quick_pow(i,k);
        if(y[i]>=mod) y[i]-=mod;
    }
    return solve(k+1,n);
}

哈希求最长等差数列

数列长度在$[1000,50000]$内，求能构成的长度在$200$以上的最长的等差数列

const int INF=1e9;
struct HashTable{
    const static int N=1e5+10;
    const static int mod=(1<<20)+1;
    int val[N],nex[N],head[mod],cnt;
    HashTable(){cnt=0;memset(head,-1,sizeof(head));}
    void add(int x){
        int left=x%mod;
        val[cnt]=x,nex[cnt]=head[left],head[left]=cnt++;
    }
    bool has(int x){
        if(x<=0 || x>INF) return 0;
        for(int i=head[x%mod];~i;i=nex[i]){if(val[i]==x) return 1;}
        return 0;
    }
}ht;
const int N=1e5+10;
int a[N];
vector<int>dat[5000005];
int getans(int x,int y,const int& preans){
    if(x==y) return 0;
    if(x>y) swap(x,y);
    int d=y-x,ans=2;
    if(d>5000000) return 0;
    for(auto i:dat[d]){if((x-i)%d==0) return 0;}
    while(ht.has(y+d)) ans++,y+=d;
    if(ans<preans){if(!ht.has(x-(preans-ans)*d)) return 0;}
    while(ht.has(x-d)) ans++,x-=d;
    if(ans>=200) dat[d].push_back(x);
    return ans;
}
void rng(int n){
    for(int i=1;i<=n;i++) swap(a[i],a[rand()%i+1]);
}
void solve(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        ht.add(a[i]);
    }
    rng(n);
    int cnt=30000000,ans=2;
    while(cnt--){
        ans=max(ans,getans(a[rand()%n+1],a[rand()%n+1],ans));
    }
    if(ans<200) printf("No Solution\n");
    else printf("%d\n",ans);
}