1462E2 - Close Tuples (hard version)（组合数）

不念不忘少年蓝@ 2021-09-03 03:53 260阅读 0赞

[题目][Link 1]

思路：先对数组排序，然后算出每个数的贡献，先从第一个数开始找到第一个大于它的值+k的数（二分），下表差即为可选的构成m个数元组的可选数的个数s，如果s<m贡献0，如果s>=m,贡献为从s-1个数中选出m-1个数的方法数（已经选了一个数）。但求组合数的模问题，不可以对两个相除的数先分别取模再除，故需要用到逆元和费马小定理先转换成乘法。不懂知道的可参考此篇博客[https://www.cnblogs.com/liziran/p/6804803.html][https_www.cnblogs.com_liziran_p_6804803.html]。

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll lst[Max], x[Max];
    const int Mod = 1e9 + 7;
    
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    
    int main()
    { 
    	FAST;int t;cin >> t;
    	x[0] = 1;
    	for (int i = 1;i <= 2e5 + 5;i++)x[i] = (x[i - 1] * i) % Mod;
    	while (t--)
    	{ 
    		ll n, m, k,sum=0;cin >> n >> m >> k;
    		for (int i = 1;i <= n;i++)cin >> lst[i];
    		sort(lst + 1, lst + 1 + n);
    		for (int i = 1;i <= n;i++)
    		{ 
    			int l = upper_bound(lst + i, lst + 1 + n, lst[i] + k) - lst;
    			int len = l - i;
    			if (len < m)continue;
    			sum = (sum + x[len - 1] * qpow(x[m - 1], Mod - 2) % Mod * qpow(x[len - m], Mod-2) % Mod)%Mod;
    		}
    		cout << sum << endl;
    	}
    }

当然直接用板子也是很爽的，[板子链接][Link 2]。

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll lst[Max], x[Max];
    const int Mod = 1e9 + 7;
    
    ll f[Max];
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    void init() { 
    	f[0] = 1;
    	for (int i = 1;i <= 2e5;i++) { 
    		f[i] = f[i - 1] * i % Mod;
    	}
    }
    ll cal(ll n, ll m) { 
    	if (n < m) return 0;
    	return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
    }
    
    
    int main()
    { 
    	FAST;int t;cin >> t;
    	init();
    	while (t--)
    	{ 
    		ll n, m, k,sum=0;cin >> n >> m >> k;
    		for (int i = 1;i <= n;i++)cin >> lst[i];
    		sort(lst + 1, lst + 1 + n);
    		for (int i = 1;i <= n;i++)
    		{ 
    			int l = upper_bound(lst + i, lst + 1 + n, lst[i] + k) - lst;
    			int len = l - i;
    			if (len < m)continue;
    			sum += cal(len - 1, m - 1);
    			sum%= Mod;
    		}
    		cout << sum << endl;
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1462/E2
[https_www.cnblogs.com_liziran_p_6804803.html]: https://www.cnblogs.com/liziran/p/6804803.html
[Link 2]: https://blog.csdn.net/asbbv/article/details/111321575