Если представить умножение в столбик, то правая единица при умножении даст ряд 100...01. Остальные нули дадут ряды нулей. Когда умножаем левую единицу тоже получаем ряд 100...01 со сдвигом влево на n-1. Складывая числа, получим вид 100...020..01, то есть n * 2 - 1 значное число, у которого двойка посередине. Пример:
101*
101
101+
000+
101=
10201
Тогда для примеров из задачи: 10001^2 = 100020001
1000001^2 = 10000020000001