理性愉悦:分段多项式函数XXX

hdu5803

$\sum_a \sum_b \sum_c \sum_d [a+c>b+d \& a+d\ge b+c]$
移项可得
$\sum_a \sum_b \sum_c \sum_d [a-b>d-c \& a-b\ge c-d]$

$f(i)=\sum_a \sum_b [a-b=i]$
$g_1(i)=\sum_c \sum_d [c-d=i]$
$g_2(i)=\sum_c \sum_d [d-c=i]$
这些都是非常简单的分段一次函数
答案类似于
$\sum_i f(i)\sum_{j\leq i}g(j)$
这样的东西

由于并不想推公式,头脑发热就想让机器自己推

洋洋洒洒361行就下去了……

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mo=1e9+7;
const LL inf=1LL<<62;
typedef vector<LL> Poly;
Poly operator*(const Poly &a,const Poly &b){
	Poly ans(a.size()+b.size()-1);
	for(int i=0;i<a.size();i++)
	for(int j=0;j<b.size();j++)
		ans[i+j]=(ans[i+j]+a[i]*b[j]%mo)%mo;
	while(ans.size()>1 && ans.back()==0)
		ans.pop_back();
	return ans;
}
Poly operator*(const Poly &a,const LL &b){
	Poly ans=a;
	for(int i=0;i<ans.size();i++)
		ans[i]=ans[i]*b%mo;
	return ans;
}
Poly operator+(const Poly &a,const Poly &b){
	Poly ans(max(a.size(),b.size()));
	for(int i=0;i<ans.size();i++){
		if(i<a.size())
			ans[i]+=a[i]%mo;
		ans[i]%=mo;
		if(i<b.size())
			ans[i]+=b[i]%mo;
		ans[i]%=mo;
	}
	return ans;
}
Poly operator-(const Poly &a,const Poly &b){
	Poly ans(max(a.size(),b.size()));
	for(int i=0;i<ans.size();i++){
		if(i<a.size())
			ans[i]+=a[i];
		ans[i]=(ans[i]+mo)%mo;
		if(i<b.size())
			ans[i]-=b[i];
		ans[i]=(ans[i]+mo)%mo;
	}
	return ans;
}
Poly operator+(const Poly &a,const LL &b){
	Poly ans=a;
	ans[0]=(ans[0]+b%mo)%mo;
	return ans;
}
Poly operator-(const Poly &a,const LL &b){
	Poly ans=a;
	ans[0]=(ans[0]+mo-b%mo)%mo;
	return ans;
}
LL compute(Poly poly,LL x){
	if(x<0)return 0;
	x=x%mo;
	LL ans=0;
	for(int i=(int)poly.size()-1;i>=0;i--)
		ans=(ans*x%mo+poly[i])%mo;
	return ans;
}
void print(Poly poly){
	for(int i=0;i<poly.size();i++){
		printf("%lldx^%lld",poly[i],i);
		putchar(i+1==poly.size()?'\n':'+');
	}
}
struct mPoly{
	LL l,r;
	Poly poly;
	LL &operator[](int x){return poly[x];}
	LL operator[](int x)const{return poly[x];}
	
	void print(){
		printf("[%lld,%lld]\n",l,r);
		::print(poly);
	}
};
bool operator<(const mPoly &a,const mPoly &b){
	return a.l<b.l;
}
LL compute(mPoly a,LL x){
	if(x<a.l || x>a.r)
		return 0;
	LL ans=0;
	x=x%mo;
	for(int i=(int)a.poly.size()-1;i>=0;i--)
		ans=(ans*x%mo+a.poly[i])%mo;
	return ans;
}
typedef vector<mPoly> multiPoly;
mPoly empty(LL l,LL r){
	mPoly ans;
	ans.l=l;
	ans.r=r;
	ans.poly.resize(1);
	ans[0]=0;
	return ans;
}
multiPoly operator+(multiPoly a,multiPoly b){
	multiPoly ans;
	if(a.back().r!=b.back().r){
		if(a.back().r<b.back().r){
			a.push_back(empty(a.back().r+1,b.back().r));
		}else{
			b.push_back(empty(b.back().r+1,a.back().r));
		}
	}
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			LL l=max(a[i].l,b[j].l);
			LL r=min(a[i].r,b[j].r);
			if(l<=r)
				ans.push_back((mPoly){l,r,a[i].poly+b[j].poly});
		}
	}
	sort(ans.begin(),ans.end());
	return ans;
}
multiPoly operator-(multiPoly a,multiPoly b){
	multiPoly ans;
	if(a.back().r!=b.back().r){
		if(a.back().r<b.back().r){
			a.push_back(empty(a.back().r+1,b.back().r));
		}else{
			b.push_back(empty(b.back().r+1,a.back().r));
		}
	}
	
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			LL l=max(a[i].l,b[j].l);
			LL r=min(a[i].r,b[j].r);
			if(l<=r)
				ans.push_back((mPoly){l,r,a[i].poly-b[j].poly});
		}
	}
	sort(ans.begin(),ans.end());
	return ans;
}
LL pw(LL x,LL k,LL p){
	LL ans=1;
	for(;k;k>>=1){
		if(k&1)ans=ans*x%p;
		x=x*x%p;
	}return ans;
}
LL inv(LL x){
	return pw(x,mo-2,mo);
}
LL St1[10][10];
LL St2[10][10];
LL C[10][10];
Poly inte(Poly a){
	Poly ans(a.size());
	for(int i=0;i<a.size();i++){
		for(int j=0;j<=i;j++){
			ans[j]+=a[i]*St2[i][j]%mo;
			ans[j]%=mo;
		}
	}
	
		
	Poly ans2(a.size()+1);
	for(int i=0;i<ans.size();i++)
		ans2[i+1]=ans[i]*inv(i+1)%mo;
	
	
	Poly ans3(a.size()+1);
	
	for(int i=0;i<ans2.size();i++){
		for(int j=0;j<=i;j++){
			ans3[j]+=St1[i][j]%mo*((i-j)%2==0?1LL:mo-1LL)%mo*ans2[i]%mo;
			ans3[j]%=mo;
		}
	}
	
	return ans3;
}
Poly E(int x,Poly a){
	Poly ans(a.size());
	for(int i=0;i<a.size();i++){
		for(int j=0;j<=i;j++){
			ans[j]+=C[i][j]*pw(x,i-j,mo)%mo*a[i]%mo;
			ans[j]%=mo;
		}		
	}
	return ans;
}
Poly Einte(Poly a){
	return E(1,inte(a));
}
mPoly Einte(mPoly a){
	mPoly ans=a;
	ans.poly=Einte(a.poly)-compute(Einte(a.poly),a.l-1);
	return ans;
}
multiPoly Einte(multiPoly a){
	LL sum=0;
	multiPoly ans;
	for(int i=0;i<a.size();i++){
		mPoly tmp=Einte(a[i]);
		tmp.poly=tmp.poly+sum;
		ans.push_back(tmp);
		sum=compute(tmp,tmp.r);
	}
	if(ans.back().r<inf){
		mPoly tmp;
		tmp.l=ans.back().r+1;
		tmp.r=inf;
		tmp.poly.resize(1);
		tmp.poly[0]=sum;
		ans.push_back(tmp);
	}
	return ans;
}
LL compute(multiPoly a,LL x){
	if(x<0)return 0;
	for(int i=0;i<a.size();i++){
	
		if(x<a[i].l)
			return 0;
	
		if(a[i].l<=x && x<=a[i].r)
			return compute(a[i],x);
	}
	
	//assert(0);
	
	return 0;//compute(a.back(),a.back().r);
}
Poly zero;
multiPoly operator*(multiPoly a,multiPoly b){
	multiPoly ans;
	if(a.back().r!=b.back().r){
		if(a.back().r<b.back().r){
			a.push_back(empty(a.back().r+1,b.back().r));
		}else{
			b.push_back(empty(b.back().r+1,a.back().r));
		}
	}	
	
	//cerr<<"sf"<<endl;
	//cerr<<a.size()<<endl;
	//cerr<<b.size()<<endl;
	
	for(int i=0;i<a.size();i++){
		int flag=0;
		for(int j=0;j<b.size();j++){
		
			//cerr<<i<<" "<<j<<endl;
			LL l=max(a[i].l,b[j].l);
			LL r=min(a[i].r,b[j].r);
			
			/*if(i==1&&j==1){
				cerr<<"One More Time One More Chance"<<endl;
				print(a[i].poly);
				print(b[j].poly);
			}*/
			
			
			if(l<=r){
				ans.push_back((mPoly){l,r,a[i].poly*b[j].poly});
				flag=1;
			}
			
			
		}
		if(flag==0){
			ans.push_back((mPoly){a[i].l,a[i].r,zero});
		}
	}
	sort(ans.begin(),ans.end());
	return ans;
}

multiPoly build(LL A,LL B){
	if(A<=B){
		multiPoly f;
		mPoly tmp;
		tmp.l=0;tmp.r=A;
		tmp.poly.resize(2);
		tmp.poly[0]=(1+A)%mo;
		tmp.poly[1]=(mo-1);
		f.push_back(tmp);
		
		return f;
		
	}else{
		multiPoly f;
		mPoly tmp;
		tmp.l=0;tmp.r=A-B;
		tmp.poly.resize(1);
		tmp.poly[0]=(1+B)%mo;
		f.push_back(tmp);
		
		if(A>=A-B+1){
			tmp.l=A-B+1;tmp.r=A;
			tmp.poly.resize(2);
			tmp.poly[0]=(1+A)%mo;
			tmp.poly[1]=(mo-1);
			f.push_back(tmp);
		}
		return f;	
	}
}
void print(multiPoly m){
	for(int i=0;i<m.size();i++)
		m[i].print();
	for(int i=0;i<=3;i++)
		printf("(%d) = %d\n",i,compute(m,i));
	puts("");
}
int main(){

	St1[0][0]=1;
	St2[0][0]=1;
	C[0][0]=1;
	for(int i=1;i<10;i++){
		St1[i][0]=0;
		St2[i][0]=0;
		C[i][0]=1;
		for(int j=1;j<10;j++){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
			St1[i][j]=((i-1)*St1[i-1][j]+St1[i-1][j-1])%mo;
			St2[i][j]=(j*St2[i-1][j]+St2[i-1][j-1])%mo;
		}
	}

	LL A,B,C,D;
	int T;cin>>T;
	while(cin>>A>>B>>C>>D){
		
		LL ans=0;
		LL ans1=0,ans2=0,ans3=0;
		multiPoly f=build(A,B);
		multiPoly g1=build(C,D);
		multiPoly g2=build(D,C);
		
		f[0].l=1;
		g1[0].l=1;
		g2[0].l=1;
		
		multiPoly tmp;
		
		//c=d
		tmp=Einte(f);
		ans1=min(C+1,D+1)%mo*compute(tmp,A)%mo;
		tmp=Einte(f*Einte(g1));
		
		ans2=compute(tmp,A)%mo;
		tmp=Einte(f*(Einte(g2)-g2));
		ans3=(compute(tmp,A)%mo)%mo;
		ans=(ans1+ans2+ans3)%mo;
		cout<<ans<<endl;
	}	
	
	return 0;
}

CF366(Div.1) E 口胡

题意:
给定一棵n个点的树,有m个老司机在树上飚车,老司机会在t_i时刻开始以速度c_i从u_i到v_i驶去,如果同一时刻两车在同一位置,那么就会出车祸,输出第一个出车祸的时间点或报告无解
(更多…)