ヌクレオチド [いろはちゃんコンテスト Day1 J]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_j

解説

https://atcoder.jp/contests/iroha2019-day1/submissions/5198838

回分なので、半分が確定すれば、もう半分も確定する。
簡単のために、Nが偶数のときを考えてみよう。
　
N/2個の01列を作るが、例えば0100だったとする。
この時、転倒数は2である。
これを反転させて、後ろにくっつければ、全体が回分となるが、
0010の転倒数は1である。
転倒数は1,0の順になっている組の個数であるが、0と1のペアを考えたときに、
ある列とそれを反転させた列のどちらかでは転倒数として必ずカウントされる。
つまり何がいいたいのかというと、「(0の個数)×(1の個数)=転倒数+反転時の転倒数」であるということ。
加えて、反転させて後ろにくっつけると、転倒数もその間で増える。
増える個数は、(0の個数)×(1の個数)である。
　
N/2個の01列で、0の個数をzero, 転倒数をtentoとする。
すると、全体の転倒数は、
tento + ( (zero × (N/2-zero) - tento ) + (zero × (N/2-zero) )
となり、これが=Kである。
うまく変形すると、
tento + ( (zero × (N/2-zero) - tento ) + (zero × (N/2-zero) ) = K
2(zero × (N/2-zero) ) = K
となり、tentoは関係なくなる。
つまり、N/2個の01列のうち、0がzero個あるものは、全体の転倒数がKとなる。
よって、このzeroを計算しよう。
これはちょうど、２次方程式になっているので、整数解を求めよう。
整数解が求まればzeroの個数がわかったことになるので、組み合わせはC(N/2,zero)通りあるので、
これを解が2つあれば、2つそれぞれ求めて、答えとなる。
　
Nが奇数の場合も若干計算式が異なるので、真ん中に0を置くか1を置くかで式を作って、
２次方程式を解いて、計算すればいい。
偶数の場合が理解できていれば、そんなに難しくはない。

Comb<mint, 202020> com;
//---------------------------------------------------------------------------------------------------
void _main() {
	int Q; cin >> Q;
	rep(q, 0, Q) {
		ll N, K;
		cin >> N >> K;
 
		if (N % 2 == 0) {
			N /= 2;
 
			ll zero1 = (N * 2 + sqrt(N * 2 * N * 2 - 4LL * 2 * K) + 0.1) / 4LL;
			ll zero2 = (N * 2 - sqrt(N * 2 * N * 2 - 4LL * 2 * K) + 0.1) / 4LL;
 
			if (2LL * (N - zero1) * zero1 != K) {
				printf("0\n");
				continue;
			}
 
			if (2LL * (N - zero2) * zero2 != K) {
				printf("0\n");
				continue;
			}
 
			mint ans = 0;
 
			if (zero1 == zero2) ans = com.aCb(N, zero1);
			else ans = com.aCb(N, zero1) + com.aCb(N, zero2);
 
			printf("%d\n", ans.get());
		}
		else {
			N /= 2;
 
			mint ans = 0;
 
			// xxxx1xxxx
			while (1) {
				ll zero1 = (N * 2 + 1 + (int)(sqrt((N * 2 + 1) * (N * 2 + 1) - 4LL * 2 * K) + 0.1)) / 4LL;
				ll zero2 = (N * 2 + 1 - (int)(sqrt((N * 2 + 1) * (N * 2 + 1) - 4LL * 2 * K) + 0.1)) / 4LL;
 
				if (2LL * (N - zero1) * zero1 + zero1 == K) {
					ans += com.aCb(N, zero1);
				}
				if (2LL * (N - zero2) * zero2 + zero2 == K and zero1 != zero2) {
					ans += com.aCb(N, zero2);
				}
				break;
			}
 
			// xxxx0xxxx
			while (1) {
				ll zero1 = (N * 2 - 1 + sqrt((N * 2 - 1) * (N * 2 - 1) - 4LL * 2 * (K-N)) + 0.1) / 4LL;
				ll zero2 = (N * 2 - 1 - sqrt((N * 2 - 1) * (N * 2 - 1) - 4LL * 2 * (K-N)) + 0.1) / 4LL;
 
				if (2LL * (N - zero1) * zero1 + N - zero1 == K) {
					ans += com.aCb(N, zero1);
				}
				if (2LL * (N - zero2) * zero2 + N - zero2 == K and zero1 != zero2) {
					ans += com.aCb(N, zero2);
				}
				break;
			}
 
			printf("%d\n", ans.get());
		}
	}
}