CF1817C

Celebrate · 2023-07-17 16:56:51 · 题解

容易发现，给多项式逐项之间做差，然后以差为新的数列再做差，一直操作下去可以得到一个等差数列（在题目中，最后可以得到等差数列的两项），这样只需要用等差数列的性质即可求出结果。

再考虑最后得到的数和原数列的关系，手玩可以发现刚好是一个组合数，直接求就可以了。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
template<typename T>inline void qr(T &x){
  x=0;char s=getchar();
  while(!isdigit(s))s=getchar();
  while(isdigit(s))x=x*10+s-48,s=getchar();
}
const int N=2500010,mod=1e9+7;
int fc[N],ifc[N];
int n,a[N],b[N];
int power(int x,int y){
  int ret=1;
  while(y){
    if(y&1)ret=1ll*ret*x%mod;
    x=1ll*x*x%mod;y>>=1;
  }
  return ret;
}
int C(int x,int y){
  return 1ll*fc[x]*ifc[y]%mod*ifc[x-y]%mod;
}
int main(){
  cin>>n;
  rep(i,0,n)qr(a[i]);
  rep(i,0,n)qr(b[i]);
  fc[0]=1;
  rep(i,1,n)fc[i]=1ll*fc[i-1]*i%mod;
  ifc[n]=power(fc[n],mod-2);
  dwn(i,n-1,0)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;
  int t=1,p1=0,p2=0,p3=0,p4=0;
  dwn(i,n-1,0){
    p1+=1ll*C(n-1,i)*t*a[i]%mod;
    p1=(p1%mod+mod)%mod;
    t*=-1;
  }
  t=1;
  dwn(i,n,1){
    p2+=1ll*C(n-1,i-1)*t*a[i]%mod;
    p2=(p2%mod+mod)%mod;
    t*=-1;
  }
  t=1;
  dwn(i,n-1,0){
    p3+=1ll*C(n-1,i)*t*b[i]%mod;
    p3=(p3%mod+mod)%mod;
    t*=-1;
  }
  t=1;
  dwn(i,n,1){
    p4+=1ll*C(n-1,i-1)*t*b[i]%mod;
    p4=(p4%mod+mod)%mod;
    t*=-1;
  }
  int d=((p2-p1)%mod+mod)%mod;
  int ans=(1ll*(p3-p1)*power(d,mod-2)%mod+mod)%mod;
  cout<<ans<<endl;
  return 0;
}