Microsoft have already entered into an agreement with Constellation Energy which pays to restart one of the reactors at three mile island. This comes with a 20yr purchase of the power from that plant.
There aren't many usable and idle nuclear power plants sitting around. It's extremely likely, as you point out, that states will soon be competing for jobs by offering land for both data centers as well as new power plants.
The best estimates I've seen but new construction of nuclear plants at 5-7 years. If this could safely be sped up then I assume big tech is already working to make it happen.
Of note, there are already some third parties/regulators working to stop big tech from capturing large shares of existing power generation[1]
[0] https://www.spglobal.com/commodityinsights/en/market-insight... [1] https://spectrum.ieee.org/amazon-data-center-nuclear-power