B擅长解密的小红同学
思路
因为每次输入会重置,求期望也就是求尝试多少次能成功,等价于求这些数字有多少种排列组合。
也就是多重排列数的问题。
多重排列数
设$S= \{n_1a_1,n_2a_2,…,n_ka_k\}$是由$n_1$个$a_1$,$n_2$个$a_2$,$n_k$个$a_k$组成的多重集。
多重集排列数
多重集$S$的全排列,不考虑相同的元素,其全排列个数为$(\sum_{i=1}^kn_i)!$,但是因为存在若干个相同的元素,因此要把相同元素的贡献给除掉。
对于每种排列的每个$a_{i,j}$,我们都可以从$n_i$个$a_i$中挑选任意一个,其对答案的贡献满足乘法原理为$n_i!$
因此方案数为
$$
\frac{(\sum_{i=1}^{k}n_i)!}{\prod_{i=0}^{k}n_i!}
$$
注意: 该题$fact[N]$, $N$能取到$10^7$, 若$infact[N]$也也算出来,复杂度达到$O(10^7 * log(10^6))$ 会超时, 所以infact[N]不需做枚举
代码
#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
typedef long long LL;
int a[10];
LL fact[N], infact[N];
LL qmi(LL a, LL b){
LL res = 1;
while(b){
if(b & 1) res = (LL)res * a % mod;
a = (LL) a * a % mod;
b >>= 1;
}
return res;
}
void init(){
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++){
fact[i] = (LL)fact[i - 1] * i % mod;
}
}
int main(){
for(int i = 0; i < 10; i ++)
cin >> a[i];
init();
LL fz = 0;
LL ans = 1;
for(int i = 0; i < 10; i ++){
fz = (LL)(fz + a[i]) % mod;
ans = (LL)ans * fact[a[i]] % mod;
}
ans = (LL)fact[fz] * qmi(ans, mod - 2) % mod;
cout << ans << endl;
return 0;
}
H 漂亮数
思路
通过两个质数相乘得到漂亮数, 可以直接打表并计算前缀和即可
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 50000010;
typedef long long LL;
LL primes[N];
int cnt;
LL st[N];
int s[N * 2];
void init(){
for(int i = 2; i < N; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; (LL)primes[j] * i < N; j ++){
st[(LL)primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
for(int i = 0; i < cnt; i ++)
for(int j = 0; j < cnt; j ++){
if((LL)primes[i] * primes[j] >= N * 2) break;
s[(LL)primes[i] * primes[j]] = 1;
}
for(int i = 1; i <= N * 2; i ++)
s[i] += s[i - 1];
}
int main(){
init();
int T;
cin >> T;
while(T --){
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
I 加减
链接:https://ac.nowcoder.com/acm/contest/11214/I
来源:牛客网
题目描述
小红拿到了一个长度为 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 次操作。她希望操作结束后,该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗?
输入描述
第一行两个正整数 和
第二行有 个正整数
$1≤n≤10^5$
$1≤k≤10^{12}$
$1≤ai≤10^9$
输出描述:
不超过 次操作之后,数组中可能出现最多次数元素的次数。
示例1
输入
5 3
6 3 20 8 1
输出
2
说明
共 3 次操作如下:
第一个数加一。
第二个数加一。
第四个数减一。
数组变成了 7 4 20 7 1 ,共有 2 个相同的数: 7 。
可以证明, 2 为最优解。另外,此上操作并不是唯一的操作。
思路(贪心,前缀和,二分)
定理: 一个数组每次操作可以让一个数加一或者减一,使所有都相等的操作最小次数的方式是所有数都变成中位数。
排序,求前缀和,枚举区间[L, R], 枚举L, 二分R, 即枚举所有排好序的区间,判断该区间是否达到该区间的中位数的操作小于等于k
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N];
LL s[N];
LL n, k;
bool check(int l, int r){
int mid = l + r >> 1;
LL left_op = a[mid] * (mid - l + 1) - (s[mid] - s[l - 1]);
LL right_op = (s[r] - s[mid]) - a[mid] * (r - mid);
return (left_op + right_op) <= k;
}
int main(){
scanf("%lld%lld", &n, &k);
for(int i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i ++)
s[i] = s[i - 1] + a[i];
int res = 1;
for(int i = 1; i <= n; i ++){
//枚举左端点
int l = i, r = n;
//二分右端点
while(l < r){
int mid = l + r + 1>> 1;
if(check(i, mid)){
l = mid;
}
else r = mid - 1;
}
res = max(res, r - i + 1);
}
cout << res << endl;
}