oj.uz

답안 #9010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9010 2014-09-27T10:33:23 Z ainta Actual visible points (kriii2_AC) C++
0 / 4
 0 ms 4620 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, w[101000];
long long Mod = 1000000007, F[201000], G[201000], Res;
long long Inv(long long a){
	long long cnt = Mod - 2, r = 1;
	while (cnt){
		if (cnt % 2){
			r = r*a%Mod;
		}
		cnt /= 2;
		a = a*a%Mod;
	}
	return r;
}
long long Gap(int a){
	if (a == 0)return 0;
	return F[a + n - 1] * Inv(F[n]) % Mod * Inv(F[a - 1]) % Mod;
}
void Do(int a){
	G[a] = (G[a] + Gap(a) - Gap(a-1) + Mod) % Mod;
	Res = (Res + G[a]) % Mod;
	int i;
	for (i = a * 2; i <= 100000; i += a){
		G[i] = (G[i] + Mod - G[a]) % Mod;
	}
}
int main()
{
	int i;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++)scanf("%d", &w[i]);
	sort(w + 1, w + m + 1);
	F[0] = 1;
	for (i = 1; i <= 200010; i++){
		F[i] = F[i - 1] * i%Mod;
	}
	for (i = 1; i <= m; i++){
		Do(w[i]);
	}
	printf("%lld\n", Res);
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 4620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -