JZOJ6641. 【GDOI20205.20模拟】sequence

Description

Solution

• 首先你需要感受出一种贪心地方法：如果p<q，那么全部都放1肯定最优，否则考虑从1到n一个一个放，如果能往右放就往右放。
• 对于$p<=q$的情况，相当于求$sum_{i=1}^{n}i^k$，拉格朗日插值可以做到$O(k)$求一次。
• 接下来考虑$p>q$。
• 那么相当于从右往左放，每一次放的尽量多，可以二分放多少，再$O(m)$判断。由于长度是$sqrt{2n}$级别的，所以这个复杂度$O(m^2logn)$并不能过。
• 结合第一种做法，二分出最右的至少能放1的位置，再二分最多能放多少个，把这个位置填最多，以及之前的位置都填最少的量。
• 如果这个位置每填1，前面就需要多填$k$，如果不考虑上取整的关系，就可以近似这么认为，那么$res$就会变成$res mod k$，因为数据随机，可以近似这么看，所以总的轮数实际上是$O(log n)$的。
• $O(m logn^2)$.

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long 
#define mo 1000000007
#define maxn 1000005
#define maxm 50005
using namespace std;

int T,i,j,k,p,q,n,m,a[maxm],b[maxm];
ll fct[maxn],invf[maxn];

ll ksm(ll x,ll y){
	ll s=1;
	for(;y;y/=2,x=x*x%mo) if (y&1)
		s=s*x%mo;
	return s;
}

int tot,pri[maxn],bz[maxn]; ll f[maxn];
void getpri(int n,int k){
	memset(bz,0,sizeof(bz)),tot=0,f[1]=1;
	for(int i=2;i<=n;i++){
		if (!bz[i]) pri[++tot]=i,f[i]=ksm(i,k);
		for(j=1;j<=tot&&i*pri[j]<=n;j++){
			bz[i*pri[j]]=1,f[i*pri[j]]=f[i]*f[pri[j]]%mo;
			if (i%pri[j]==0) break;
		}
	}
	for(int i=1;i<=n;i++) f[i]=(f[i]+f[i-1])%mo;
}

ll pre[maxn],nex[maxn];
ll Get(int n,int k){
	pre[0]=1,nex[k]=1;
	for(i=1;i<=k;i++) pre[i]=pre[i-1]*(n-i+1)%mo;
	for(i=k-1;i>=0;i--) nex[i]=nex[i+1]*(n-i-1)%mo;
	ll sum=0;
	for(i=0;i<=k;i++) {
		if ((k-i)&1) 
			sum-=f[i]*pre[i]%mo*nex[i]%mo*invf[i]%mo*invf[k-i]%mo;
		else sum+=f[i]*pre[i]%mo*nex[i]%mo*invf[i]%mo*invf[k-i]%mo;
	}
	return sum%mo;
}

int check(int x,int d){
	for(int i=1;i<=m;i++) b[i]=a[i];
	b[x]+=d; ll sum=d;
	for(int i=x-1;i>=1&&1ll*b[i]*q<1ll*b[i+1]*p;i--){
		sum+=ceil(1.0*b[i+1]*p/q)-b[i];
		if (sum>n) return 0;
		b[i]=ceil(1.0*b[i+1]*p/q);
	}
	return 1;
}

void put(int x,int d){
	a[x]+=d,n-=d;
	for(int i=x-1;i>=1&&1ll*a[i]*q<1ll*a[i+1]*p;i--){
		n-=ceil(1.0*a[i+1]*p/q)-a[i];
		a[i]=ceil(1.0*a[i+1]*p/q);
	}
}

ll doit(){
	memset(a,0,sizeof(a));
	m=sqrt(n*2); int tp=1;
	while (n){
		int l=1,r=m,mid,id=0,mx;
		while (l<=r) {
			mid=(l+r)>>1;
			if (check(mid,1)) l=mid+1,id=mid;
			else r=mid-1;
		}
		if (tp) m=id,tp=0;
		l=1,r=n,mx=0; 
		while (l<=r) {
			mid=(l+r)>>1;
			if (check(id,mid)) l=mid+1,mx=mid;
			else r=mid-1;
		}
		put(id,mx);
	}
	ll ans=0;
	for(i=1;i<=m;i++)  
		ans+=ksm(i,k)*a[i]%mo;
	return ans%mo;
}

int main(){
	scanf("%d",&T);
	fct[0]=1; for(i=1;i<maxn;i++) fct[i]=fct[i-1]*i%mo;
	invf[maxn-1]=ksm(fct[maxn-1],mo-2);
	for(i=maxn-2;i>=0;i--) invf[i]=invf[i+1]*(i+1)%mo;
	while (T--){
		scanf("%d%d%d%d",&n,&k,&p,&q);
		if (p<=q) {
			getpri(k+1,k);
			printf("%lld
",(Get(n,k+1)+mo)%mo); 
		} else printf("%lld
",doit());
	}
}