Ira and Flamenco

题意：

给一个数组，你要选m个数，且其中最大-最小要小于m，求方案数mod1e9+7。

思路：

先记录每个数出现的次数，再用set给数组排序去重一下。对于合法的m个数，其选择方案数就是每个数的数量乘起来。然后枚举每个合法区间即可，求区间方案数，可以用前缀和来求，具体看代码。

代码：

int n, a[maxn];int m;int qmi(int a, int b){int ans = 1;while(b){if(b & 1)ans = (ans * a) % mod;b >>= 1;a = (a * a) % mod;}return ans;}void solve(){cin >> n >> m;map<int, int> mp;set<int> s;for(int i = 1; i <= n; i ++ ){cin >> a[i];mp[a[i]] ++ ;s.insert(a[i]);}n = s.size();vector<int> num(n + 1);num[0] = 1;int cnt = 0;vector<int> b(n + 1);for(auto i : s){cnt++;b[cnt] = i;num[cnt] = num[cnt - 1] * mp[i] % mod;}int ans = 0;for(int i = m; i <= n; i ++ )if(b[i] - b[i - m + 1] < m)ans = (ans + num[i] * qmi(num[i - m], mod - 2) % mod) % mod;cout << ans << endl;}

如果觉得《Ira and Flamenco》对你有帮助，请点赞、收藏，并留下你的观点哦！