【牛客7872 A】离散化-求一个数列第b项是第a项的多少倍
题意
一个数列,初值为1,递推公式为
求第b项是第a项的多少倍,a和b的范围是1e8,1e5组询问
显然可以初始处理出第1项~第1e8项的值(取模)
然后取我们需要的,取的这个过程需要离散化一下提高效率,把所有询问到的点存在一个c数组里,排个序,在初始处理的时候碰到这个数组里的值就把这个答案记下来
初始化完成后就可以对每一组询问计算答案即可
哔哔赖赖
据说还可以map搞一下,下次再说咕咕咕
Code
/**************************** * Author : W.A.R * * Date : 2020-10-31-22:27 * ****************************/ /* */ #include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<stack> #include<string> #include<set> #define IOS ios::sync_with_stdio(false) #define show(x) std:: cerr << #x << " = " << x << std::endl; #define mem(a,x) memset(a,x,sizeof(a)) #define Rint register int using namespace std; typedef long long ll; const int maxn=1e6+10; const int maxm=2e6+10; const ll mod=1e9+7; const double PI=acos(-1.0); const double eps=1e-7; ll qpow(ll a,ll n){a%=mod;ll ans=1;while(n){if(n%2)ans=ans*a%mod;n/=2;a=a*a%mod;}return ans;} ll a[maxn],b[maxn],c[maxn],ans[maxn]; int main(){ int T=read(),ct=0; for(int i=1;i<=T;i++)a[i]=read_ll(),b[i]=read_ll(),c[++ct]=a[i],c[++ct]=b[i]; sort(c+1,c+1+ct); ct=unique(c+1,c+1+ct)-c-1; show(ct); int index=1; ll x=1; for(int i=0;i<=1e8;i++){ if(i!=0)x=(x*x%mod+x%mod)%mod; if(index<=ct&&c[index]==i)ans[index]=x,index++; } for(int i=1;i<=T;i++){ if(a[i]>b[i])swap(a[i],b[i]); int fa=lower_bound(c+1,c+1+ct,a[i])-c; int fb=lower_bound(c+1,c+1+ct,b[i])-c; show(ans[fa]); show(ans[fb]); printf("%lld\n",ans[fb]*qpow(ans[fa],mod-2)%mod); } return 0; }