codeforces 839d Winter is here

一场给dalao们吐槽到不行。全场B题最后终测挂了9/10的div2。
hack频频出错。B题比D题还难的场。。
多校中插一脚cf。hhhhhhh

题目传送门

题意：
给一个序列，要求找一个可以不连续长度为k的子序列满足下标$i_1 < i_2 < i_3 < ... < i_k$
有满足$p = gcd(a_{i_{1}},a_{i_{2}}..a_{i_{k}}), p > 1$可以贡献p * k的价值。
现在问对于这个序列的所有情况的贡献是多少。

思路：
其实可以不要被这个下标蒙蔽了。下标没什么的。只是限定你只能使用一次这个序列而已。
比赛的时候发现其实对于每一个位置答案就是$i * \sum i * C_{n}^{i}$ ，这里的n为这个数与这个数的倍数的总和。
然后答案可能有重复容斥一下就好了（本人容斥比较弱。就写过两次。估计如果比赛真要写容斥，脑子抽的话容斥怎么写都不对）
然后发现$i * C_{n}^{i}$这个东西怎么那么难算啊。算不出啊。是不是思路错了。。然后就挂机一个钟了
其实dalao都说。不难发现。$C_{n}^{i} = C_{n - 1}^{i - 1} * n / i$
所以$i * C_{n}^{i} = n * C_{n - 1}^{i - 1}$
然后$\sum C_{n - 1}^{i - 1} 明显等于2^{n - 1}$
所以最后转换成$n * 2^{n - 1}$ 即可

代码如下：

/* @resources: codeforces 839d @date: 2017-08-13 @author: QuanQqqqq @algorithm: 容斥 */
#include <bits/stdc++.h>#define ll long long
#define MAXN 2000005
#define MOD 1000000007using namespace std;ll tot[MAXN], mark[MAXN];
ll c[MAXN];ll ksm(ll a, ll n) {ll ans = 1, t = a;while (n) {if (n & 1) {ans = (t * ans) % MOD;}t = (t * t) % MOD;n >>= 1;}   return ans;
}int main() {ll n, maxt = 0, tmp;scanf("%lld", &n);for (ll i = 0; i < n; i++) {scanf("%lld", &tmp);tot[tmp]++;maxt = max(maxt, tmp);}for (ll i = 2; i <= maxt; i++) {ll sum = 0;for (ll j = i; j <= maxt; j += i) {sum += tot[j];}if (sum == 0) {continue;}if (mark[sum] != 0) {c[i] = mark[sum];continue;}c[i] = (sum * ksm(2, sum - 1)) % MOD;mark[sum] = c[i];}ll ans = 0;for (ll i = maxt; i >= 2; i--) {for (ll j = i * 2; j <= maxt; j += i) {c[i] -= c[j];c[i] = (c[i] % MOD + MOD) % MOD;}ans += (c[i] * i) % MOD;ans %= MOD;}printf("%lld\n", ans);
}