fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sd(x) scanf("%d", &x)
  6. #define F first
  7. #define S second
  8. #define PB push_back
  9. #define MP make_pair
  10.  
  11. typedef pair<int, int> pii;
  12. typedef pair< pii, pii > QT;
  13. typedef long long int LL;
  14.  
  15. #define rep(i, j, k) for(int i = j; i < k; ++i)
  16.  
  17. #define N 112345
  18. #define M 2123456
  19. #define B 350
  20. #define MOD 1000000007
  21.  
  22. inline void norm(int &x){
  23. 	if(x >= MOD){
  24. 		x -= MOD;
  25. 	}
  26. 	if(x < 0){
  27. 		x += MOD;
  28. 	}
  29. }
  30.  
  31. inline LL powerMod(LL a, LL p, LL mod){
  32. 	LL ret = 1;
  33. 	a %= mod;
  34. 	while(p > 0){
  35. 		if(p & 1){
  36. 			ret *= a;
  37. 			ret %= mod;
  38. 		}
  39. 		p >>= 1;
  40. 		a *= a;
  41. 		a %= mod;
  42. 	}
  43. 	return ret;
  44. }
  45.  
  46. bool comp(QT a, QT b){
  47. 	if(a.F.F / B == b.F.F / B){
  48. 		return a.F.S < b.F.S;
  49. 	}
  50. 	return a.F.F < b.F.F;
  51. }
  52.  
  53. vector<int> divs[N];
  54. int mu[N], spf[N];
  55. LL fac[N], ifac[N];
  56.  
  57. inline LL com(int n, int r){
  58. 	if(n < r){
  59. 		return 0;
  60. 	}
  61. 	LL ret = fac[n];
  62. 	ret *= ifac[r];
  63. 	ret %= MOD;
  64. 	ret *= ifac[n - r];
  65. 	ret %= MOD;
  66. 	return ret;
  67. }
  68.  
  69. inline void pre(){
  70. 	mu[1] = 1;
  71. 	fac[1] = 1;
  72. 	fac[0] = 1;
  73. 	rep(i, 2, N){
  74. 		fac[i] = (fac[i - 1] * i) % MOD;
  75. 		if(spf[i] == 0){
  76. 			spf[i] = i;
  77. 			for(int j = i; j < N; j += i){
  78. 				spf[j] = i;
  79. 			}
  80. 		}
  81. 		mu[i] = - mu[i / spf[i]];
  82. 		if((i / spf[i]) % spf[i] == 0){
  83. 			mu[i] = 0;
  84. 		}
  85. 	}
  86. 	int x = 0;
  87. 	ifac[N - 1] = powerMod(fac[N - 1], MOD - 2, MOD);
  88. 	rep(i, 1, N){
  89. 		ifac[N - i - 1] = (ifac[N - i] * (N - i)) % MOD;
  90. 		if(mu[i] != 0){
  91. 			if(i <= 10000){
  92. 				x++;
  93. 			}
  94. 			for(int j = i; j < N; j += i){
  95. 				divs[j].PB(i);
  96. 			}
  97. 		}
  98. 	}
  99. }
  100.  
  101. bool alive[M];
  102. int id[N], rid[M], cnt[N], sz;
  103. int cntp[N], cntn[N];
  104.  
  105. inline void add(int k, int x){
  106. 	if(k < B){
  107. 		if(mu[x] == 1){
  108. 			cntp[k]++;
  109. 		}
  110. 		else{
  111. 			cntn[k]++;
  112. 		}
  113. 		return;
  114. 	}
  115. 	id[x] = sz;
  116. 	rid[sz] = x;
  117. 	alive[sz] = true;
  118. 	sz++;
  119. }
  120.  
  121. inline void rem(int k, int x){
  122. 	if(k < B){
  123. 		if(mu[x] == 1){
  124. 			cntp[k]--;
  125. 		}
  126. 		else{
  127. 			cntn[k]--;
  128. 		}
  129. 		return;
  130. 	}
  131. 	alive[id[x]] = false;
  132. }
  133.  
  134. inline void inc(int x){
  135. 	if(cnt[x] >= B){
  136. 		cnt[x]++;
  137. 		return;
  138. 	}
  139. 	rem(cnt[x], x);
  140. 	cnt[x]++;
  141. 	add(cnt[x], x);
  142. }
  143.  
  144. inline void dec(int x){
  145. 	if(cnt[x] >= B + 1){
  146. 		cnt[x]--;
  147. 		return;
  148. 	}
  149. 	rem(cnt[x], x);
  150. 	cnt[x]--;
  151. 	add(cnt[x], x);
  152. }
  153.  
  154. inline void incad(int x){
  155. 	rep(i, 0, divs[x].size()){
  156. 		inc(divs[x][i]);
  157. 	}
  158. }
  159.  
  160. inline void decad(int x){
  161. 	rep(i, 0, divs[x].size()){
  162. 		dec(divs[x][i]);
  163. 	}
  164. }
  165.  
  166. int ans[N], a[N];
  167. QT query[N];
  168.  
  169. int main(){
  170. 	pre();
  171. 	int n, q, l, r, cl, cr, ck, ci, csz, k;
  172. 	sd(n);
  173. 	rep(i, 1, n + 1){
  174. 		sd(a[i]);
  175. 	}
  176. 	sd(q);
  177. 	rep(i, 0, q){
  178. 		sd(query[i].F.F); sd(query[i].F.S); sd(query[i].S.F);
  179. 		query[i].S.S = i;
  180. 	}
  181. 	sort(query, query + q, comp);
  182. 	l = r = 1;
  183. 	sz = 0;
  184. 	incad(a[1]);
  185. 	rep(i, 0, q){
  186. 		cl = query[i].F.F;
  187. 		cr = query[i].F.S;
  188. 		ck = query[i].S.F;
  189. 		ci = query[i].S.S;
  190. 		while(r < cr){
  191. 			incad(a[r + 1]);
  192. 			r++;
  193. 		}	
  194. 		while(l > cl){
  195. 			incad(a[l - 1]);
  196. 			--l;
  197. 		}
  198. 		while(l < cl){
  199. 			decad(a[l]);
  200. 			l++;
  201. 		}
  202. 		while(r > cr){
  203. 			decad(a[r]);
  204. 			--r;
  205. 		}
  206. 		ans[ci] = 0;
  207. 		rep(j, ck, B){
  208. 			if(cntp[j] - cntn[j] != 0){
  209. 				ans[ci] += (com(j, ck) * (cntp[j] - cntn[j])) % MOD;
  210. 				norm(ans[ci]);
  211. 			}
  212. 		}
  213. 		csz = 0;
  214. 		rep(j, 0, sz){
  215. 			if(alive[j] == true){
  216. 				k = rid[j];
  217. 				rid[csz] = k;
  218. 				id[k] = csz;
  219. 				alive[csz] = true;
  220. 				csz++;
  221. 				if(mu[k] == 0 || cnt[k] < ck){
  222. 					continue;
  223. 				}
  224. 				if(mu[k] == 1){
  225. 					ans[ci] += com(cnt[k], ck);
  226. 					norm(ans[ci]);
  227. 				}
  228. 				else{
  229. 					ans[ci] -= com(cnt[k], ck);
  230. 					norm(ans[ci]);
  231. 				}
  232. 			}
  233. 		}
  234. 		sz = csz;
  235. 	}
  236. 	rep(i, 0, q){
  237. 		printf("%d\n", ans[i]);
  238. 	}
  239. 	return 0;
  240. }
  241.  
Time limit exceeded #stdin #stdout 15s 26792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6PCujU
10
1 2 3 4 5 6 7 8 9 10
3
1 5 2
1 10 3
1 10 4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!