Uniquely Solvable One-Dimensional Minesweeper
National Olympiad — Regional round (2023 season)
Submission name: minesweeper.cpp
Problem summary
Count binary mine rows of length N uniquely determined by their safe lower-row neighbour clues, modulo10^9+7.
Input
One integer N.
Output
The uniquely recoverable-layout count modulo1000000007.
Constraints
1≤N≤100000.
Worked example
Input and output for the worked example discussed below.
Input
2
Output
2
Solution analysis
- For two rows giving the same clues, their difference d satisfies d[i−1]+d[i]+d[i+1]=0 with zero padding. The left boundary forces the repeating patternδ,−δ,0.
- The right boundary permits nonzeroδ only when N=3k+2. For all other lengths every one of the2^N layouts is unique. A nonzero binary difference hasδ=±1.
- For N=3k+2, one ambiguity family fixes positions1 mod3 to1 and2 mod3 to0; the reverse family swaps these bits. The k remaining positions are free. Subtract2^(k+1) ambiguous rows from2^N. For N=2 only00 and11 remain unique, giving2.
Why it works
The clue equations propagate the entire difference from its first value. Boundary compatibility allows precisely the two described nonzero-difference families at lengths≡2mod3. They are disjoint and each has2^k layouts, so the subtraction formula counts exactly unique rows.
Watch out. Count mine layouts, not clue strings. Subtract only at N mod3=2 and normalize the modular residue.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
// The clue equations propagate the entire difference from its first value.
const long long modulo=1000000007;
long long power(int n){
long long value=2,result=1;
while(n>0){
if(n%2){
result=result*value%modulo;
}
value=value*value%modulo;
n/=2;
}
return result;
}
int main(){
int n;
cin>>n;
long long answer=power(n);
if(n%3==2){
answer=(answer-power(n/3+1)+modulo)%modulo;
}
cout<<answer<<'\n';
}