集团网站建设 中企动力,响应式网站开发教程,网站改了模板被百度降权,如何免费制作自己的网站题源
题目 F. 预期中位数 每次测试的时间限制#xff1a;3 秒 每次测试的内存限制#xff1a;256 兆字节 Arul 有一个长度为 n 的二进制数组* a。 他将取该数组中所有长度为 k#xff08;k 为奇数#xff09;的子序列并找到它们的中位数。 所有这些值的总和是多少#xf…题源
题目 F. 预期中位数 每次测试的时间限制3 秒 每次测试的内存限制256 兆字节 Arul 有一个长度为 n 的二进制数组* a。 他将取该数组中所有长度为 kk 为奇数的子序列并找到它们的中位数。 所有这些值的总和是多少 由于这个和可能非常大因此输出它对 109° 7 取模的结果。换句话说打印该和除以 10° 7 后的余数。 二进制数组是仅由零和一组成的数组。 † 如果数组 b 可以通过从 a 中删除几个可能是零个或全部元素来获得则数组 b 是数组 a 的子序列。子序列不必是连续的。 奇数长度 k 的数组的中位数是排序后的第 1 个元素。2 输入第一行包含一个整数 t1 ≤ t ≤ 104表示测试用例的数量。 每条测试用例第一行包含两个整数n和k1≤k≤n≤2105k为奇数分别为数组的长度和子序列 每个测试用例的第二行包含 n 个整数 ai (0 a 1)——数组的元素。 保证所有测试用例的 n 之和不超过 2.105。 输出 对于每个测试用例打印模 109 7 的总和。 题目分析
基础的组合数问题不需要多少分析针对每一种1占据多数的子字符串情况进行组合数目加和就可以主要是算法空间时间复杂度的问题
解答
由于不知道更优时间复杂度的算法懒我一直在套用旧的组合数板子 时间空间复杂度都是 O ( n 2 ) 时间空间复杂度都是O(n^2) 时间空间复杂度都是O(n2)
ll Mod;
const ll N 5e3 100;
ll comb[N][N];
auto setMod [](ll n 1e9 7) {Mod n;
};
void get_comb(int n) {for (int i 0; i n; i)for (int j 0; j i; j)comb[i][j] (0 j j i) ? (comb[i - 1][j - 1] comb[i - 1][j]) % Mod : 1;
}
int C(int n, int m) {if (n m m -1) return 1; //* 隔板法特判if (n m || m 0) return 0;return comb[n][m];
}
/// 加法递推求组合数O(n^2)模数非素数时可用完整代码
新的板子 O log n 时间复杂度如果不看初始化 O ( n ) 的话 O n 空间时间复杂度的算法 O\log n时间复杂度如果不看初始化O(n)的话\newline On空间时间复杂度的算法 Ologn时间复杂度如果不看初始化O(n)的话On空间时间复杂度的算法
ll Mod 1e9 7;
const ll N 3e5 7;auto setMod [](ll n 1e9 7) {Mod n;
};//快速幂模板fusk power template
ll qpow(ll a, ll k) {ll ans 1;while (k) {if (k 1)ans 1LL * a * ans % Mod;k 1;a 1LL * a * a % Mod;}return ans;
}
//组合数模板combination number templatevectorll fact(N, 1);
void ini(ll n) {rep(i, 1, n) {fact[i] (fact[i - 1] * i) % Mod;}
}
ll C(ll n, ll k) {if (n k)return 0ll;return fact[n] * qpow((fact[n - k] * fact[k]) % Mod, Mod - 2) % Mod;
}
