Submission #830926

#	Time	Username	Problem	Language	Result	Execution time	Memory
830926		rainboy	Party (INOI20_party)	C11	7 / 100	310 ms	340 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	200
#define MD	1000000007

int inv(int a) {
	return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}

int main() {
	int q;

	scanf("%d", &q);
	while (q--) {
		static int pp2[N + 1], dd[N + 1], qu[N], kk[N];
		long long n;
		int cnt, h, i, j, s, d, ans;

		scanf("%lld", &n);
		pp2[0] = 1;
		for (i = 1; i <= n; i++)
			pp2[i] = pp2[i - 1] * 2 % MD;
		ans = 0;
		for (s = 1; s <= n; s++) {
			for (i = 1; i <= n; i++)
				dd[i] = n;
			cnt = 0;
			dd[s] = 0, qu[cnt++] = s;
			for (h = 0; h < cnt; h++) {
				i = qu[h], d = dd[i] + 1;
				if ((j = i >> 1) > 0 && dd[j] > d)
					dd[j] = d, qu[cnt++] = j;
				if ((j = i << 1 | 0) <= n && dd[j] > d)
					dd[j] = d, qu[cnt++] = j;
				if ((j = i << 1 | 1) <= n && dd[j] > d)
					dd[j] = d, qu[cnt++] = j;
			}
			memset(kk, 0, n * sizeof *kk);
			for (i = 1; i <= n; i++)
				kk[dd[i]]++;
			for (d = 1; d < n; d++)
				kk[d] += kk[d - 1];
			for (d = 0; d < n; d++)
				ans = (ans + pp2[n - kk[d]] - 1) % MD;
		}
		printf("%lld\n", (long long) ans * inv(pp2[n] - 1) % MD);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:20:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37