Problemi con Johnnie Walker (walker)

Non capisco proprio dove sbaglio. Potete per favore aiutarmi? Grazie.

#include <fstream>
using namespace std;
int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n,k,i,j;
	int p=1;
	in>>n>>k;
	j=n-1;
	i=k-1;
	cout<<n<<k<<endl;
	for(i=k-1;i!=0;i--){
		p=(p*j)%666013;
		j=n-2;;
}
	out<<(p %666013);
	

	
	
}

Ho provato con dei valori e mi portano tutti. Non capisco allora dove sbaglio. Mi da 0/100.

Ciao! Jonnie può ripassare sull’incrocio 1 durante il percorso, l’unica restrizione è che l’incrocio successivo sia ogni volta diverso dal precedente, quindi quel j=n-2; è sbagliato.
Tuttavia anche mettendo j=n-1 sarebbe sbagliato, in quanto il penultimo incrocio visitato non può essere l’1. Ti consiglio di ragionarci un momento, magari provare prima la dp in O(k) e poi cercare una formula matematica chiusa per fare 100.
Ah e stai attento a quando moltiplichi due interi che potresti avere problemi di overflow :upside_down_face:

Il personaggio però può ritornare ad un incrocio che ha già visitato?

Ho provato a fare così ma non va lo stesso (0 su 100):

#include <iostream>
#include <fstream>
using namespace std;
int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n,k,i,j;
	int p=1;
	in>>n>>k;
	p=n-1;
	for(i=k-2;i!=0;i--){
		if(k-i==+1) p*=n-3;
		else p*=n-2;
	}
	out<<(p %666013);
}

Questo non è l’approccio corretto per eseguire il problema. Con quel for stai eseguendo di fatto una potenza, per la precisione (n-2)^k-3 * (n-3). Lasciando perdere che concettualmente la soluzione è sbagliata, se guardi i constraints (cioè le limitazioni dell’input date dal problema), ti accorgi che l’operazione è troppo grande da fare. Considera che N arriva fino a 10^9 e K arriva a 10^18 , in pratica il numero finale può arrivare ad avere 9*10^19 cifre!

La formula chiusa risolutiva non è così semplice purtroppo, almeno non quella che ho trovato, e per ricavarla bisogna avere una certa dimestichezza con le serie e tener presente che tutti i numeri diversi da 1 sono indistinguibili fra loro ma si distinguono tutti dal numero 1 anche perchè: