ファイル case(N=1000).txt が与えられ、数列の要素 a_i をいくつか min(a_i, 1000 - a_i) で置き換えて全要素のxorを最小にするとき、置き換えた結果の数列の種類数を 10^9+7 で割った余りを要求された。
[今見ている要素][これまでのxorの結果] を状態としてメモ化探索を行い、まずxorの結果の最小値を求め、続いてその最小値になる数列の種類数を求めるプログラムを作成した。
このプログラムに case(N=1000).txt の内容を入力として与えることで、flagが得られた。
A file case(N=1000).txt was given, and the number of sequence that can be obtained by replacing some elements a_i with min(a_i, 1000 - a_i) to minimize xor of all elements was asked. (The number modulo 10^9+7 should be answered)
I wrote a program to perform search with memoization using status [the position of the element looking at][result of xor so far] to firstly obtain the minimum value of xor, and then obtain the number of sequences to achieve the value.
I obtained the flag by feeding the content of the file case(N=1000).txt as the input to this program.