Submission #39108354

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e6+10,LIM=1e6,mod=1e9+7;
void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
ll mypow(ll a,ll n){
	if(!n)return 1;
	ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;
	if(n&1)tmp=tmp*a%mod;return tmp;
}
ll myinv(ll a){return mypow(a,mod-2);}

ll fact[MAXN],rfact[MAXN];
void pre(){
	fact[0]=1;
	rep(i,1,LIM)fact[i]=fact[i-1]*i%mod;
	rfact[LIM]=myinv(fact[LIM]);
	per(i,LIM-1,0)rfact[i]=rfact[i+1]*(i+1)%mod;
}
ll C(ll n,ll m){
	if(n<m || m<0)return 0;
	return fact[n]*rfact[m]%mod*rfact[n-m]%mod;
}
ll P(ll n){return (n%2)?(mod-1):(1);}

ll n,m,L,R,ans;

namespace CFM{
	ll G[MAXN];
	ll F(ll V,ll S){
		//前面m个取[0,V]和为S的方案数
		if(S<0)return 0;
		ll res=0;
		rep(i,0,m)if(i*(V+1)>S)break;else{
			ll rest=S-i*(V+1);
			ll num=P(i)*C(m,i)%mod;
			num=num*G[rest]%mod;
			
			add(res,num);
		}
		return res;
	}
	ll calc(ll x,ll k){ //a[m]=x
		ll res=F(x,k-(n-m)*(x+1));
		if(x){
			sub(res,F(x-1,k-(n-m)*(x+1)));
		}
		return res;
	}
	ll solve(ll k){ //和不超过k	
		//分母(1-x)^{-(n+1)}
		ll ans=C(n+k,k); //总数

		rep(i,0,k)G[i]=C(n+i,i);

		//去掉xm不等于xm+1的

		rep(a,0,k){

			sub(ans,calc(a,k)*C(n,m)%mod);
		}

		return ans;
	}
}
int main(){
	pre();

	cin>>n>>m>>L>>R;
	m=n-m;
	
	add(ans,CFM::solve(R));
	sub(ans,CFM::solve(L-1));

	cout<<ans<<endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll mypow(ll, ll)’:
./Main.cpp:21:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   21 |  if(n&1)tmp=tmp*a%mod;return tmp;
      |  ^~
./Main.cpp:21:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   21 |  if(n&1)tmp=tmp*a%mod;return tmp;
      |                       ^~~~~~

Judge Result