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 
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è: