OMC112

黄色になりました
■OMC112(A)
頑張る
■OMC112(D)
包除原理。
以下を手計算で2^5ケース頑張る

void OMC112D() {
	vector<long long>v = { 101,107,113,131,137 };
	long long ans = 0;
	rep(i, 1 << 5) {
		long long x = 1;
		long long y = 1;
		rep(j, 5) {
			if (1 & (i >> j))x *= v[j];
			else y *= v[j];
		}
		long long z;// (3n+1)-(3n+2)
		if (1 == y % 3)z = y - y / 3;
		else z = -(y + 1) / 3;
		if (0 == popcount(i) % 2) {
			if (1 == x % 3) ans += z * x;
			else ans -= z * x;
		}
		else {
			if (1 == x % 3) ans -= z * x;
			else ans += z * x;
		}
	}
	cout << ans << endl;
}

■OMC112(F)
求めるものは
合計::
14*(1i+2 j+3k+4l+5m+6n)%7*6!/(i!*j!*k!....)*30!/((6-i)!*(6-j)!*...):｛0<=i,j,k,l,m,n<=6,i+j+k+l+m+n=6}
総数::
36!/(6!)^6
なので整理すると
ans = 14/36C6*Σ(1i+2 j+3k+4l+5m+6n)%7*6Ci*6Cj*6Ck*6Cl*6Cm*6Cn:｛0<=i,j,k,l,m,n<=6,i+j+k+l+m+n=6}
が求まれば良い
つまりはこう。

void OMC112F() {
	vector<long long>v = { 1,6,15,20,15,6,1 };
	long long ans = 0;
	rep(i, 7)rep(j, 7)rep(k, 7)rep(l, 7)rep(m, 7)rep(n, 7) {
		if (6 != (i + j + k + l + m + n))continue;
		long long x = v[i] * v[j] * v[k] * v[l] * v[m] * v[n];
		long long y = 1 * i + 2 * j + 3 * k + 4 * l + 5 * m + 6 * n;
		y %= 7;
		ans += x * y;
	}
	ans *= 14;
	long long y = 1947792;// 36C6
	long long g = gcd(ans, y);
	cout << ans / g << "/" << y / g << endl;
}

これだと7^6なので手計算ができないので整理すると
考えるケースは高々11パターンなので

void OMC112F_2() {
	vector<long long>c = { 1,6,15,20,15,6,1 };
	long long ans = 0;
	vector<vector<int>>table = {
		{0 ,0 ,0 ,0 ,0 ,6 },
		{0, 0 ,0 ,0 ,1 ,5 },
		{0 ,0 ,0 ,0 ,2 ,4 },
		{0 ,0 ,0 ,0 ,3 ,3 },
		{0 ,0 ,0 ,1 ,1 ,4 },
		{0 ,0 ,0 ,1 ,2 ,3 },
		{0 ,0 ,0 ,2 ,2 ,2 },
		{0 ,0 ,1 ,1 ,1 ,3 },
		{0 ,0 ,1 ,1 ,2 ,2 },
		{0 ,1 ,1 ,1 ,1 ,2 },
		{1 ,1 ,1 ,1 ,1 ,1 }
	};
	rep(i, table.size()) {
		long long x = 1;
		rep(j, 6)x *= c[table[i][j]];
		long long y = 0;
		do {
			int sum = 0;
			rep(j, 6) sum += (j + 1) * table[i][j];
			y += sum % 7;
		} while (next_permutation(table[i].begin(), table[i].end()));
		ans += x * y;
	}
	ans *= 14;
	long long y = 1947792;// 36C6
	long long g = gcd(ans, y);
	cout << ans / g << "/" << y / g << endl;
}

とわかる。
さらに整理すると

void OMC112F_3() {
	vector<long long>c = { 1,6,15,20,15,6,1 };
	long long ans = 0;
	vector<vector<int>>table = {
		{0 ,0 ,0 ,0 ,0 ,6 },
		{0, 0 ,0 ,0 ,1 ,5 },
		{0 ,0 ,0 ,0 ,2 ,4 },
		{0 ,0 ,0 ,0 ,3 ,3 },
		{0 ,0 ,0 ,1 ,1 ,4 },
		{0 ,0 ,0 ,1 ,2 ,3 },
		{0 ,0 ,0 ,2 ,2 ,2 },
		{0 ,0 ,1 ,1 ,1 ,3 },
		{0 ,0 ,1 ,1 ,2 ,2 },
		{0 ,1 ,1 ,1 ,1 ,2 },
		{1 ,1 ,1 ,1 ,1 ,1 }
	};
	rep(i, table.size()) {
		long long x = 1;
		rep(j, 6)x *= c[table[i][j]];
		long long y = 0;
		do {
			int sum = 0;
			rep(j, 6) sum += (j + 1) * table[i][j];
			if (0 != sum % 7)y++;
		} while (next_permutation(table[i].begin(), table[i].end()));
		ans += x * (y / 2 * 7);
	}
	ans *= 14;
	long long y = 1947792;// 36C6
	long long g = gcd(ans, y);
	cout << ans / g << "/" << y / g << endl;
}

こうなる。これぐらいならどうにかなるはずと信じて手計算を頑張る