noip模拟69(待补)

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll mod=1e9+7;

ll A,B,C,D,Ri,Rj,ans;
inline ll gcd(ll x,ll y){
	if(!(x and y)) return x+y;
	ll tmp; while(tmp=y) y=x%y,x=tmp;
	return x;
}
signed main(){
	File(hacker);
	A=read(),B=read(),C=read(),D=read();
	ll lc,rc;
	for(int i=1;i<=999;i++){
		ll li=A/i+(A%i>0),ri=B/i;
		for(int j=1;j<=999-i;j++){
			if(gcd(i,j) xor 1) continue;
			ll lj=C/j+(C%j>0),rj=D/j;
			lc=max(li,lj),rc=min(ri,rj);
			if(lc>rc) continue;
			ans=(ans+(rc-lc+1)*(i+j)%mod)%mod;
		}
	}
	printf("%lld\n",ans%mod),exit(0);
}

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	auto read=[]()->ll{
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	};
} using namespace BSS;

const ll N=503,M=103,W=(1<<9)+5;
const ll P=100000000000000000;

ll m,n,s,U;
ll b1[M],b2[M],ban[W],num[W],bin[W][20],cnt[W];
struct Huge{
	ll len; ll r[63];
	inline friend Huge operator +(const Huge &x,const Huge &y){
		Huge c; ll tmp=0; c.len=max(x.len,y.len),Fill(c.r,0);
		for(int i=1;i<=c.len;i++){	
			c.r[i]=x.r[i]+y.r[i]+tmp;
			tmp=c.r[i]/P,c.r[i]%=P;
		}
		if(tmp) c.r[++c.len]=tmp;
		return c;
	}
	inline friend Huge operator *(Huge x,ll y){
		ll tmp=0;
		for(int i=1;i<=x.len;i++){
			x.r[i]=x.r[i]*y+tmp,tmp=x.r[i]/P,x.r[i]%=P;
		}
		if(tmp) x.r[++x.len]=tmp; return x;
	}
}anscnt,ansval,f[N][W],g[N][W];
auto print=[](Huge c)->void{
	printf("%lld",c.r[c.len]);
	for(int i=c.len-1;i>=1;i--){
		printf("%017lld",c.r[i]);
	}
	puts("");
};
signed main(){
	File(hacker2); 
	n=read(),m=read(),s=read(),U=(1<<s)-1;
	for(int i=1;i<=m;i++) 
		b1[i]=read(),b2[i]=read(),ban[1<<b1[i]-1]|=1<<b2[i]-1;
	for(int i=0;i<=U;i++){
		for(int S=i;S;(--S)&=i)
			ban[i]|=ban[S];
		for(int j=1;j<=s;j++){
			if((1<<j-1)&ban[i]) continue;
			bin[i][++cnt[i]]=j;
		}
	}
	f[0][0].r[1]=1,f[0][0].len=1;
	for(int i=0;i<=U;i++) g[0][i].len=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=U;j++){
			// cout<<j<<" cnt_j:"<<cnt[j]<<endl;
			for(int k=1;k<=cnt[j];k++){
				f[i+1][j|(1<<bin[j][k]-1)]=f[i+1][j|(1<<bin[j][k]-1)]+f[i][j];
				// cout<<i+1<<' '<<(j|(1<<bin[j][k]-1))<<' '<<i<<' '<<j<<endl;
				// print(g[i+1][j|(1<<bin[j][k]-1)]),print(g[i][j]);
				g[i+1][j|(1<<bin[j][k]-1)]=g[i+1][j|(1<<bin[j][k]-1)]+g[i][j]*10ll+f[i][j]*bin[j][k];
			}
		}
	}
	for(int i=1;i<=U;i++) anscnt=anscnt+f[n][i];
	// cout<<"NOW:"<<endl;
	for(int i=1;i<=U;i++) ansval=ansval+g[n][i];//print(ansval),print(g[n][i]);	
	print(anscnt); print(ansval);	
	exit(0);
}