首页 > 代码库 > Atcoder arc077 D - 11 组合
Atcoder arc077 D - 11 组合
Link
题意:给出n个数,其中有一个数会出现两次,其余数只出现一次,问不同长度且不同的子串的数量。取模1e9+7
思路:组合求出所有情况,减去重复情况,注意用逆元即可
/** @Date : 2017-07-06 09:56:44 * @FileName: atcoder077 D 组合.cpp * @Platform: Windows * @Author : Lweleth (SoungEarlf@gmail.com) * @Link : https://github.com/ * @Version : $Id$ */#include <bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const LL mod = 1e9 + 7;LL a[N];LL inv[N];LL fa[N];LL n;void init(){ fa[0] = fa[1] = 1; inv[1] = 1; for(LL i = 2; i < N; i++) { fa[i] = fa[i-1] * i % mod; inv[i] = (mod - mod / i) * inv[mod % i] % mod; } inv[0] = 1; for(int i = 1; i < N; i++) (inv[i] *= inv[i - 1]) %= mod;}LL C(LL n, LL k){ LL ans = 0; if(k > n) return ans; ans = ((fa[n] * inv[k] % mod) * inv[n - k]) % mod; return ans;}int main(){ init(); while(cin >> n) { map<LL, int>q; LL p = 0; for(int i = 1; i <= n + 1; i++) { scanf("%lld", a + i); if(!q[a[i]]) q[a[i]] = i; else p = i; } for(int i = 0; i <= n; i++) { LL ans = 0; ans = (ans + C(n + 1, i + 1)) % mod; ans = (ans - C(n - p + q[a[p]], i)) % mod; while(ans < 0) ans += mod; printf("%lld\n", ans); } } return 0;}
Atcoder arc077 D - 11 组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。