/ XMU_ACM /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 111ms 27.957 MiB

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	ll s=0,t=1;
	char ch=getchar();
	while(!isdigit(ch))ch=='-'?ch=getchar(),t=-1:ch=getchar();
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return s*t;
}
const ll p=1e9+7;
ll n,m;
ll kkk[10],ans1[10],ans2[10],stdp[10];
ll emm[363000][10];
inline void take(ll x,ll q[]){
	for(int i=n;i>=1;i--){
		q[i]+=x/kkk[i];
		x%=kkk[i];
	}
}
inline void value(ll x[],ll y[]){
	for(int i=1;i<=9;i++)x[i]=y[i];
}
inline void kkkkkkkk(){
	kkk[1]=1;
	for(int i=2;i<=n;i++)kkk[i]=kkk[i-1]*i;
	for(int i=1;i<kkk[n];i++)take(i,stdp),value(emm[i],emm[i-1]),take(i,emm[i]);
}
inline ll em(ll x){
	x%=p;
	if(x<0)x+=p;
	return x;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)emm[0][i]=0;
	m=read();
	kkkkkkkk();
	while(m--){
		for(int i=1;i<=n;i++)ans1[i]=ans2[i]=0;
		ll x=read()-1,y=read();
		value(ans1,emm[x%kkk[n]]);
		value(ans2,emm[y%kkk[n]]);
		for(int i=1;i<n;i++)ans1[i]+=x/kkk[n]%p*stdp[i]%p,ans2[i]+=y/kkk[n]%p*stdp[i]%p;
		ll x1=(x+1)/kkk[n]-1,y1=(y+1)/kkk[n]-1;
		if(x1%2==1)x1=(1+x1)/2%p*(x1%p)%p;
		else x1=x1/2%p*((1+x1)%p)%p;
		if(y1%2==1)y1=(1+y1)/2%p*(y1%p)%p;
		else y1=y1/2%p*((1+y1)%p)%p;
		ans1[n]+=x1*kkk[n]%p+((x+1)/kkk[n])%p*((x+1)%kkk[n])%p;
		ans2[n]+=y1*kkk[n]%p+((y+1)/kkk[n])%p*((y+1)%kkk[n])%p;
		for(int i=1;i<n;i++)cout<<em(ans2[i]-ans1[i])<<" ";
		cout<<em(ans2[n]-ans1[n])<<endl;
	}
	return 0;
}

信息

递交者
类型
自测
题目
P1097 集大校赛E-复杂量筒
语言
C++
递交时间
2021-06-13 18:08:15
评测时间
2021-06-13 18:08:15
评测机
分数
10
总耗时
111ms
峰值内存
27.957 MiB