1475E Advertising Agency(组合数)

ゞ浴缸里的玫瑰 2021-09-07 06:05 250阅读 0赞

[题目][Link 1]

思路：选出K个博主，要使得总共关注者最大，  
先看一个简单例子如1 2 2 3 4 4 4 4 5 6 7 7 k=6最大为4+4+5+6+7+7=33.可以知道我们一定要选最大的后面6个博主 4 4 5 6 7 7 假设换了前面一个必然导致和不为最大值，而这六个博主其实5 6 7 7也已经定死了，能选择的只有4（第n-k+1个博主的值）我们只需从总共的4个拥有4个关注者的博主选两个答案为C 4 2=4\*3/2=6。再推广到普遍情况设第K大博主关注者数量为t，答案为：所有关注者数量为t的博主中选出前k大博主中关注者数量为t的博主的数量个，即总共值为t的个数中选出最大k个中值为t的个数个。

[组合数模板][Link 2]

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<fstream>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    int Mod = 1e9 + 7;
    ll lst[Max];
    
    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--)
    	{ 
    		int n, k;cin >> n >> k;
    		map<ll, ll> ma;
    		for (int i = 1;i <= n;i++)
    		{ 
    			cin >> lst[i];
    			ma[lst[i]]++;
    		}
    		sort(lst + 1, lst + 1 + n);
    		ll p = lst[n - k + 1];
    		ll sum = 0;
    		for (int i = n - k + 1;i <= n;i++)
    		{ 
    			if (lst[i] == p)sum++;
    		}
    		cout << cal(ma[p], sum) % Mod << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1475/E
[Link 2]: https://blog.csdn.net/asbbv/article/details/111321575