1 条题解

  • 0
    @ 2023-6-21 20:06:45

    C++ :

    #pragma GCC optimize ("O2")
    #include<cstdio>
    #define ll long long
    const int N=1e5+5,M=2e5+5,mo=1e9+7;
    int rn,n,m,i,j,ans;
    int fact[M],inv[M],fv[M];
    void init(int n){
    	fact[0]=fact[1]=inv[1]=fv[0]=fv[1]=1;
    	for (i=2;i<=n;i++){
    		fact[i]=(ll)fact[i-1]*i%mo;
    		inv[i]=(ll)inv[mo%i]*(mo-mo/i)%mo;
    		fv[i]=(ll)fv[i-1]*inv[i]%mo;
    	}
    }
    int cal(int k){
    	int n=rn+k-1,m=rn-1;
    	return (ll)fact[n]*fv[m]%mo*fv[n-m]%mo;
    }
    int sum,f[N],dp[N];
    void solve(){
    	dp[0]=1;f[0]=1;
    	for (i=1;i<=n;i++){
    		sum+=i;if (sum>m) break;
    		for (j=m;j>=sum;j--){
    			dp[j]=-dp[j-i];
    			if (j>=n+1) dp[j]=(dp[j]+dp[j-n-1])%mo;
    		}
    		for (;j>=sum-i;j--) dp[j]=0;
    		for (j=sum;j<=m;j++){
    			dp[j]=(dp[j]+dp[j-i])%mo;
    			f[j]=(f[j]+dp[j])%mo;
    		}
    	}
    }
    int main(){
    	scanf("%d%d",&n,&m);rn=n;
    	init(n+m);solve();
    	for (i=0;i<=m;i++)
    		ans=(ans+(ll)f[i]*cal(m-i))%mo;
    	printf("%d",(ans+mo)%mo);
    }
    
    • 1

    #6077. 「2017 山东一轮集训 Day7」逆序对

    信息

    ID
    1033
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者