自己提供域名做网站,制作手机主题的app,wordpress 固定链接,公司网站建设 公司简介怎么写牛客网题目 题目描述 给出一个长度为n的序列#xff0c;你需要计算出所有长度为k的子序列中#xff0c;除最大最小数之外所有数的乘积相乘的结果 输入描述: 第一行一个整数T#xff0c;表示数据组数。 对于每组数据#xff0c;第一行两个整数N#xff0c;k#xff0c;含义…牛客网题目 题目描述 给出一个长度为n的序列你需要计算出所有长度为k的子序列中除最大最小数之外所有数的乘积相乘的结果 输入描述: 第一行一个整数T表示数据组数。 对于每组数据第一行两个整数Nk含义如题所示 接下来一行N个整数表示给出的序列 保证序列内的数互不相同 输出描述: 对于每组数据输出一个整数表示答案对109 7 取模 每组数据之间以换行分割 示例1 输入
3
4 3
5 3 1 4
5 4
3 7 5 2 1
10 3
100 1020 2050 102 12 235 4 57 32135 54354 输出
144
81000
521918013说明 第一组数据解释 所有长度为3的子序列为 (5,3,1) (5,3,4) (3,1,4) (5,1,4) 最终答案为3∗4∗3∗41443 题解 对于子序列一个数aa会以三种形式存在 1.最大值 2.最小值 3.中间值 我们现将序列从小到大排序从0开始并不影响结果但是有利于计算 a在长度为 k 的子序列中出现的次数为 Ck−1n−1(因为如果它出现在子序列中那么总数还有 n−1 个 数字序列的长度还有 k−1 个) 对于第一种情况a作为最大值的下表为ia之前的i个数都比a小所选出的子序列一定有以下标i为结尾的我们需要从前i个中选出k-1个组成长度为k的子序列个数为Ck-1i(组合数 同理ai 是最小值的情况的方法数为 Ck−1n−i−1 piCk−1n−1−Ck−1i−Ck−1n−i−1 对于 ai这个数来说它对答案的贡献为 apii 最终的答案为 ans∏n−1i0apii
#include iostream
#include algorithm
#include string.h
#include stdio.h
#include stdlib.h
using namespace std;
typedef long long LL;
const LL MOD 1e97;
const int MAXN 1e35;
int a[MAXN];
LL Pow(LL a, LL b)
{LL ans 1;while(b){if(b1) ansans*a%MOD;b1;aa*a%MOD;}return ans;
}LL c[MAXN][MAXN];
void Init()
{memset(c, 0, sizeof c);for(int i0; iMAXN; i){c[i][0] 1;for(int j1; ji; j){c[i][j] (c[i-1][j] c[i-1][j-1]) % (MOD-1);}}
}int main()
{Init();int T; cinT;while(T--){int n, k; cinnk;for(int i0; in; i) cina[i];sort(a, an);LL tmp c[n-1][k-1];LL ans 1;for(int i0; in; i){LL b tmp-c[i][k-1]-c[n-i-1][k-1];b (b%(MOD-1)(MOD-1))%(MOD-1);ans ans*Pow(a[i], b)%MOD;}coutansendl;}return 0;
}
因为那个是指数比如说 ab%p可以用费马小定理 a(b%(p-1)) % p
