CROC 2016 - Elimination Round (Rated Unofficial Edition) F - Cowslip Collections 数论 + 容斥

59 阅读 0 评论 39 点赞

我是靠谱客的博主伶俐玉米，最近开发中收集的这篇文章主要介绍CROC 2016 - Elimination Round (Rated Unofficial Edition) F - Cowslip Collections 数论 + 容斥，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

F - Cowslip Collections

http://codeforces.com/blog/entry/43868 这个题解讲的很好。。。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
LL inv[N], f[N], finv[N], phi[N];
int n, k, q, a[N], in[N], cnt[N];
vector<int> fac[N];
void init() {
inv[1] = f[0] = finv[0] = 1;
for(int i = 2; i < N; i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
for(int i = 1; i < N; i++) f[i] = f[i-1]*i%mod;
for(int i = 1; i < N; i++) finv[i] = finv[i-1]*inv[i]%mod;
iota(phi, phi + N, 0);
for(int i = 1; i < N; i++) {
for(int j = i; j < N; j += i) {
if(i != j) phi[j] -= phi[i];
if(in[j]) fac[j].push_back(i);
}
}
}
LL comb(int n, int m) {
if(n < m || n < 0) return 0;
return f[n]*finv[n-m]%mod*finv[m]%mod;
}
int main() {
scanf("%d%d%d", &n, &k, &q);
for(int i = 1; i <= n + q; i++) scanf("%d", &a[i]), in[a[i]] = 1;
init();
LL ans = 0;
for(int i = 1; i <= n + q; i++) {
for(int t : fac[a[i]]) {
ans = (ans + phi[t]*((comb(cnt[t]+1, k)-comb(cnt[t], k)+mod)%mod)%mod)%mod;
cnt[t]++;
}
if(i > n) printf("%lldn", ans);
}
return 0;
}
/*
*/