Mηνιαία Πρόκληση: Ιανουάριος 2021

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από AndreasRasvanis »

Καλή Χρονιά σε ολούς, συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Iανουάριο.

Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.

Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.

Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!

Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Φεβρουαριού εν προκειμένω.

Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.

(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").

Από τη σύσκεψη Δεκεμβρίου έχει επιλεγεί ήδη ο Ανδρέας (εγώ) ως βοηθός Ιανουαρίου ο οποίος εφτιαξε και ολόκληρο βίντεο εξηγώντας το προβλημα και την λύση του (θα δοθεί μετά την κλήση).

Σε αυτό το πρόβλημα έχουμε έναν δρόμο οπού έχει 2 πλέυρες, και κάθε πλευρά είναι χωρισμένη σε Ν κομμάτια (sections).

Θέλουμε σε κάθε πλευρά (ανεξάρτητα), κάθε ένα από τα Ν κομμάτια είτε να το αφήσουμε κένο είτε να χτίσουμε ένα κτήριο. Πρέπει όμως να ισχύει ότι σε κάθε πλευρά δε μπορούν να υπάρχουν 2 συνεχόμενα κτήρια χτισμένα δίπλα δίπλα.

Στόχος μας είναι να βρούμε τους συνολικούς πλήθος τρόπων να χτίσουμε κτήρια καθώς και να ισχύουν οι παραπάνω περιορισμοί.
Θα ισχύει Ν<=2^60. Επειδή το αποτέλεσμα μπορεί να είναι πολύ μεγάλο, θέλουμε να τυπώσουμε το υπόλοιπο της ακέραιας διαίρεσής του (modulo) με το (10^9+7).

Παραδείγματα

Αν Ν=1 τότε υπάρχουν 4 τρόποι.

Ας πούμε Κ το κενό κομμάτι και B αυτό που έχει χτισμένο κτήριο.

Τοτέ μπορούμε να κάνουμε τα παρακάτω 4:

Πρώτη πλευρά: Δέυτερη πλευρά:
K K
B B
B K
K B

Αν Ν=2 τότε υπάρχουν 9 τρόποι:

Πρώτη πλευρά: Δέυτερη πλευρά:
KΚ KΚ
ΚΚ ΒΚ
ΚΚ ΚΒ
KΒ KΚ
ΚΒ ΒΚ
ΚΒ ΚΒ
ΒΚ KΚ
ΒΚ ΒΚ
ΒΚ ΚΒ
Όπως βλέπετε δεν μπορούμε να βάλουμε ΒΒ.

Bonus πληροφορία: Το παραπάνω πρόβλημα μπορεί να λυθεί σε Ο(log N) χρόνο. Δοκιμάστε αρχικά να πετύχετε χρόνο Ο(Ν), και κατόπιν οτιδήποτε καλύτερο (έστω κι αν δεν είναι Ο(log N)).

Στις 20 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.

Καλή επιτυχία!
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από AndreasRasvanis »

Καλησπέρα μόλις τώρα ήρθε η courier και έφερε τα hint όχι σαν τις άλλες φορες που άργησε λόγω covid

1) Δείξτε ότι αν γνωρίζαμε τους τρόπους να βάλουμε κτήρια στη μία πλευρά του δρόμου, θα μπορούσαμε αυτόματα να υπολογίσουμε τη λύση στο πρόβλημά μας.
2) Ας επικεντρωθούμε μόνο στη μία πλευρά του δρόμου. Θέλουμε να υπολογίσουμε αναδρομικά τη λύση μας. Υπάρχουν δύο βασικές προσεγγίσεις (και οι 2 στηρίζονται στο να εξετάσουμε αν θα μπει ή δε θα μπει κτήριο στην τελευταία θέση.
Α) Πρέπει να υπολογίσουμε αναδρομικά τα
-Πλήθος_Τρόπων(Ν οικόπεδα, Χτίζω κτήριο στο τελευταίο οικόπεδο)
-Πλήθος_Τρόπων(Ν οικόπεδα, Δε χτίζω κτήριο στο τελευταίο οικόπεδο)
Β) Πρέπει να υπολογίσουμε αναδρομικά το
-Πλήθος_Τρόπων(Ν οικόπεδα)
Διαλέξτε όποιο απ' το (Α) ή (Β) σας φαίνεται πιο προσιτό, και προσπαθήστε να βρείτε μια αναδρομική σχέση για αυτό.

Για όποιον δεν ξέρει τι ακριβώς είναι οι αναδρομικές σχέσεις, θα θέλαμε, για το (Α) κάτι του τύπου:
Πλήθος_Τρόπων(Ν οικόπεδα, Χτίζω) = Πλήθος_Τρόπων(Ν-1 οικόπεδα, Δε χτίζω) + Πλήθος_Τρόπων(Ν-2 οικόπεδα, Χτίζω)
κι αντίστοιχα μια τέτοια σχέση για το Πλήθος_Τρόπων(Ν οικόπεδα, Δε χτίζω).
Τονίζω ότι η σχέση που έχω γράψει είναι λάθος, απλά περιμένουμε ότι κάπως έτσι μοιάζει η μορφή της σωστής, και πρέπει να βάλετε τη λογική σας για να καταλάβετε πώς ακριβώς θα μοιάζει.

Καλή επιτυχία σε όλους.
kostas1507
Δημοσιεύσεις: 31
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από kostas1507 »

Υπάρχει κάποιο λάθος με την εκφώνηση ή δεν καταλαβαίνω κάτι; 2^60 είναι ο μεγαλύτερος αριθμός κομματιών ή ο μεγαλύτερος αριθμός του πλήθους τρόπων; Γιατί αν είναι ο αριθμός κομματιών, οι πιθανοί συνδυασμοί θα είναι μεγαλύτερος αριθμός από ότι χωράει σε οποιοδήποτε τύπο δεδομένων με πολύ μεγάλη διαφορά..
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από switch »

2^60 ειναι το μεγιστο οριου αριθμου κομματιών. Το πληθος διαφορετικών συνδιασμων ειναι οπως ειπες πολυ μεγαλυτερο αλλα δεν μας το ζητα οποτε δεν χρειαζεται να το αποθηκευσεις. Αντι αυτου πρεπει να επιστρεψεις το υπολοιπο της διαίρεσης του με καποιον πρωτο αριθμο πχ 10^9+7.

Αν δεν καταλαβες τι σημασια εχει το υπολοιπο της διαιρεσης, δες πχ εδω:
https://www.geeksforgeeks.org/modular-arithmetic/
kostas1507
Δημοσιεύσεις: 31
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από kostas1507 »

πως θα μπορούσα να μην αποθηκέψω τον αριθμό;
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από switch »

Αποθηκευεις σε long long οταν εχεις υπολογισει για κ κομματια και κανεις modulo με 10^9+7.
Tον ακριβη αριθμο δεν τον χρειαζεσαι, μονο το υπόλοιπο.
Μετα υπολογιζεις για κ+1 και προσαυξανεις αναλογα τον long long σου ξανακανοντας modulo .
Με τον τροπο αυτο δεν προκειται να χρειαστεις περισσοτερο απο 64 bits (η τελικη απαντηση χωρα σε 32bits αλλα θελεις το long long για να μην κανεις overflow μεχρι να κανεις το modulo)
kostas1507
Δημοσιεύσεις: 31
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από kostas1507 »

οκ ευχαριστώ!
AndreasRasvanis
Δημοσιεύσεις: 6
Εγγραφή: Τρί Δεκ 22, 2020 3:46 pm

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από AndreasRasvanis »

Καλησπέρα σε όλους!

Η συνάντηση θα γίνει το επόμενο Σάββατο, 30 Ιανουαρίου, 15:00 ώρα Ελλάδος.
Το link για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09

Meeting ID: 675 8682 5824
Passcode: 988982

Μην ξεχάσετε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στον ασπροπίνακα, καθώς η online έκδοση δε δίνει τέτοια δυνατότητα.

Τα λέμε τότε!
Άβαταρ μέλους
switch
Δημοσιεύσεις: 83
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Mηνιαία Πρόκληση: Ιανουάριος 2021

Δημοσίευση από switch »

Να γράψω λύση ή να μη γράψω; Ιδού η απορία!
:mrgreen:

Πολλές φορές οι κώδικες που κυκλοφορούν για λύσεις σε προβλήματα διαγωνισμών και μη, είναι κατανοητοί μόνο από αυτούς που ... ξέρουν ήδη να λύσουν τα αντίστοιχα προβλήματα :D

Ένας κώδικας (ειδικά ενός διαγωνιζόμενου) είναι τόσο σύντομος και συχνά ακαταλαβίστικος και δεν βοηθά την κατανόηση της λύσης. Ο λόγος που γίνεται αυτό είναι γιατί ο λύτης έχει πιθανότατα χρησιμοποιήσει ένα σύνολο γνώσεων στη λύση του, με σκοπό το συντομότερο σε κώδικα ή πολυπλοκότητα αποτέλεσμα. Αυτές οι "ταρζανιές" μπορεί να αποθαρρύνουν τους νεαρούς μαθητές που δεν έχουν την ανάλογη γνώση και άνεση στο χειρισμό της γλώσσας, να ξέρετε όμως ότι αυτές οι ταρζανιές δεν είναι πάντα απαραίτητες και πολλές φορές με μοναδικό κόστος την αύξηση των γραμμών του κώδικα, μπορούν οι ίδιες λειτουργίες να γραφτούν πιο απλά.

Ας αρχίσουμε τη συζήτηση πάνω στο πρόβλημα μας. (ουφ, επιτέλους :roll: )

Στο συγκεκριμένο πρόβλημα, η ύπαρξη δυο δρόμων είναι ένα κερασάκι στο γλυκό, είναι το επιδόρπιο και δεν χρειάζεται να μας απασχολεί παρά μόνο στο τέλος. Αρκεί να βρούμε τους συνδυασμούς για τον ΕΝΑ δρόμο και να τον υψώσουμε στο τετράγωνο. Αν έχουμε δηλαδή k συνδυασμούς για τον ένα δρόμο, τότε έχουμε άλλους k για τον άλλο. Πόσοι είναι οι συνδυασμοί και για τους δύο δρόμους; για κάθε έναν από τους k συνδυασμούς του ενός δρόμου, έχουμε k συνδυασμούς από τον άλλο δρόμο. Αρα για τους k συνδυασμούς του πρώτου δρόμου, έχουμε συνολικά k*k συνδυασμούς με τους δύο δρόμους μαζί.

Ας δούμε ποια είναι η αρχική ιδέα αν θέλουμε να λύσουμε το πρόβλημα με τον ένα δρόμο, όχι προσπαθώντας να ακολουθήσουμε το γνωστό τύπο για εύρεση του ν-οστού όρου της γνωστής ακολουθίας (ονόματα δε λέμε), αλλά με pure δυναμικό προγραμματισμό.

Ο δυναμικός προγραμματισμός είναι μια αξιοποίηση της επαγωγικής μεθόδου που διδάσκεται στο γυμνάσιο (αν δεν κάνω λάθος):
α) υπολογίζω την αρχική τιμή (για το μικρότερο δυνατό πρόβλημα, συνήθως ενός στοιχείου) και
β) υπολογίζω την τιμή για i+1 αν ξέρω ήδη την απάντηση για i στοιχεία.
Οπότε όπως καταλαβαίνετε εφόσον ξέρουμε την απάντηση για Ν==1 (από το (α)), μπορούμε να βρούμε το επόμενο για Ν==2 (από το (β)) και το επόμενο για Ν==3 (από το (β)) κλπ

Γραμμική λύση Ο(Ν):
α) αν έχουμε 1 τμήμα δρόμου, έχουμε μόνο δυο συνδυασμούς (building=κτήριο ή void=κενό)
β) ας υπολογίσουμε πόσοι συνδυασμοί θα υπάρχουν για k+1 τμήματα.
Για κάθε αριστερό κομμάτι δρόμου k τμημάτων, τότε θα προσθέσουμε ένα ακόμα τμήμα (και να πάμε στα k+1 τμήματα). Το νέο τμήμα αυτό αν θα είναι void, θα έχει όσους συνδυασμούς είχαμε για τα k τμήματα (ανεξάρτητα αν τελείωναν σε building ή void).
Αν το νέο τμήμα είναι building, θα έχουμε όσους συνδυασμούς είχαμε για τα k τμήματα και τελείωναν σε void.
Το άθροισμα των δυο τιμών είναι οι συνολικοί συνδυασμοί των k+1 τμημάτων.

Λογαριθμική λύση O(logN):
Στην προηγούμενη λύση, ανεβαίναμε ένα ένα τα τμήματα μέχρι να φτάσουμε στα Ν του προβλήματος. Οι γραμμικές λύσεις για Ν γύρω στο 10^6, απαιτούν περίπου 1 δευτερόλεπτο. Αν το N όμως είναι 2^63 (περίπου 10^19), δεν αρκεί η παραπάνω λύση. Για μεγάλα Ν πρέπει να σκαρφαλώνουμε πιο γρήγορα στο Ν.
Η διαφορά από την προηγούμενη (γραμμική) μέθοδο, είναι ότι θέλω να προσθέτω μπλοκ δρόμου με άλλο μπλοκ δρόμου (μπλοκ = δρόμος με ένα ή περισσότερα διαδοχικά τμήματα). Προφανώς για να ενώσουμε δύο μπλόκ δεν θα πρέπει το πρώτο μπλοκ να τελειώνει σε building και το δεύτερο να αρχίζει από building. Άρα πρέπει να κρατάμε ΧΩΡΙΣΤΑ για κάθε υπολογισμένο μπλοκ, πόσοι συνδυασμοί:
  • ξεκινούν από void και τελειώνουν σε void και
  • ξεκινούν από void και τελειώνουν σε building και
  • ξεκινούν από building και τελειώνουν σε void και
  • ξεκινούν από building και τελειώνουν σε building
οπότε όταν συνδυάζουμε δυο μπλοκ, θα ξαναϋπολογίζουμε τις τέσσερις νέες τιμές του νεοϋπολογιζόμενου μεγαλύτερου μπλοκ.

Μια σημείωση ακόμα στη συνένωση δυο μπλόκ: αν από το πρώτο μπλόκ είχαμε a συνδυασμούς από building σε void και από το δεύτερο μπλοκ b συνδυασμούς από building σε building, τότε στο συνενωμένο δρόμο θα πρέπει να προσθέσουμε άλλους a*b συνδυασμούς σε αυτούς που ξεκινούν από building και τελειώνουν σε building (γιατί για οποιοδήποτε συνδυασμό του πρώτου δρόμου από τους a, έχουμε b συνδυασμούς από τον δεύτερο δρόμο, άρα συνολικά a*b συνδυασμούς)

Μια λογαριθμική λύση είναι να διαιρώ το Ν δια δύο μέχρι να φτάσω στο 1 (top down programming: ξεκινάμε από το συνολικό πρόβλημα και κόβουμε συνεχώς σε μικρότερα).
Spoiler: show

Κώδικας: Επιλογή όλων

//https://www.pdpforum.eu.org/forum/viewtopic.php?f=3&p=9738#p9738
//dp, matrix exponantiation, fibonacci, binary exponantiation
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

typedef long long ll;
const ll MOD = 1000007LL;
ll N = 19;//ll(1e18);

struct segm {
	bool init;
	ll sol[2][2];//sol[start_digit][end_digit], digits in {0=empty,1=building}
	segm(){memset(this,0,sizeof(*this));}
	ll count() const {
		ll ans = 0;
		for(int i=0;i<=1;i++){
			for(int j=0;j<=1;j++){
				ans += sol[i][j];
				if(ans>=MOD)
					ans -= MOD;
			}
		}
		return ans;
	}
};

map<int,segm> S;

inline ll trunc(ll x){ return x % MOD; }

segm combine(const segm& A,const segm& B){
	segm res;
	for(int start=0;start<=1;start++){//start res (start of combined segment)
		for(int stop=0;stop<=1;stop++){//stop res (stop of combined segment)
			for(int aend=0;aend<=1;aend++){//end of first subseg
				for(int bstart=0;bstart<=1;bstart++){//start of second subseg
					if(aend && bstart)//unaccepted: two consequtive buildings
						continue;
					ll r1 = trunc(A.sol[start][aend]);
					ll r2 = trunc(B.sol[bstart][stop]);
					res.sol[start][stop] += trunc(r1*r2);
					if(res.sol[start][stop]>=MOD)
						res.sol[start][stop]-=MOD;
				}
			}
		}
	}
	return res;
}

segm solve(int n){
	if(!S[n].init){
		if(n==1){
			S[1].sol[0][0] = S[1].sol[1][1] = 1;
		} else {
			if(n&1)
				S[n] = combine(solve(n>>1),solve((n>>1)+1));
				//what about n/2+1 plus n/2?
			else
				S[n] = combine(solve(n>>1),solve(n>>1));
		}
		S[n].init = true;
	}
	return S[n];	
}

int main(){
	ll ans = solve(n).count();
	printf("n=%d, 1road=%lld, 2roads=%lld\n",n,ans,trunc(ans*ans));
	return 0;
}

Μια εναλλακτική λογαριθμική λύση είναι να προϋπολογίσουμε μπλοκ δρόμων με μήκος δυνάμεις του 2 και μετά να συνθέσουμε τα μπλόκ για να φτάσουμε στο Ν (bottom up programming).
(ΣΣ οποιοσδήποτε φυσικός αριθμός μπορεί να γραφτεί σαν άθροισμα δυνάμεων του 2, αυτό μάλιστα χρησιμοποιεί και η συνήθης τεχνολογία των υπολογιστών -μέχρι τώρα- για την αναπαράσταση αριθμών και την ονομάζουμε δυαδικό σύστημα).

Αρα προϋπολογίζουμε τους συνδυασμούς για 1,2,4,8,16,32,64,128,... (χωρίς να ξεπεράσουμε το Ν διότι δεν θα μας χρησιμεύσει).

Ποια μπλόκ θα συνδυάσουμε για τον Ν μήκους δρόμο;
Όσες από τις παραπάνω δυνάμεις του 2 έχουν άθροισμα ακριβώς Ν. Είναι δύσκολο αυτό να το βρούμε; Όχι βέβαια, αρκεί να δούμε την αναπαράσταση του Ν στο δυαδικό σύστημα.
π.χ. ο αριθμός Ν = 1000 (στο δεκαδικό σύστημα), είναι o 001111101000(στο δυαδικό)
Spoiler: show
ή ο 0χ3E8 στο δεκαεξαδικό
Άρα αν ελέγχουμε τα bit με ένα loop ένα προς ένα, κάθε φορά που φτάνουμε σε ένα Bit με τιμή 1, προσθέτουμε στο μπλοκ της τελικής λύσης μας και την αντίστοιχη δύναμη.
Spoiler: show

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;
ll N = 19;
const ll MOD = 10000007LL;

ll t(ll x){
	return x % MOD;
}

struct seg {
	ll s[2][2];
	seg(){
		memset(this,0,sizeof(*this));
	}
	ll sum() const {
		ll ans = 0;
		for (int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				ans += s[i][j];
		return t(ans);
	}
} dp[8*sizeof(ll)];

seg combine(const seg& a,const seg& b){
	seg ans;
	for(int astart=0;astart<2;astart++)
		for(int bend=0;bend<2;bend++)
			for (int i=0;i<2;i++)//aend
				for(int j=0;j<2;j++){//bstart
					if(i && j) continue;
					ans.s[astart][bend] += t(a.s[astart][i]*b.s[j][bend]);
					if(ans.s[astart][bend]>=MOD)
						ans.s[astart][bend]-=MOD;
				}
	return ans;
}

int main(){
	dp[0].s[0][0] = dp[0].s[1][1] = 1;//dp[0] stands for length==1
	for(ll i=1,length=2;length<=N;i++,length*=2){
		dp[i] = combine(dp[i-1],dp[i-1]);
	}

	seg ans;
	int count = 0;
	for(ll i=0,length=1; length<=N;i++,length*=2){
		if(N & length){
			if(count++ == 0)
				ans = dp[i];
			else
				ans = combine(ans,dp[i]);
		}
	}
	
	printf("1road=%lld\t2roads=%lld\n",ans.sum(),t(ans.sum() * ans.sum()));
	return 0;
}
Spoiler: show

Κώδικας: Επιλογή όλων

//https://www.pdpforum.eu.org/forum/viewtopic.php?f=3&p=9738#p9738
//tags: dp, matrix exponentiation, fibonacci, binary exponentiation
//current solution: binary exponentiation
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;
const ll MOD = 1000007LL;
ll N = 19;//ll(1e18);

//building=1, void=0
ll dp[8 * sizeof(ll) * 2][2][2];	/*[number of long long bits * 2][startofsegment][endofsegment]*/
ll sum[8 * sizeof(ll) * 2];

inline ll t(ll x){ return x % MOD; }

void combine(int dest,int seg1,int seg2){
	//combine segment dp[seg1][i][j] with dp[seg2][k][l] to dp[dest][i][l]
	sum[dest] = 0ll;
	for(int i=0;i<2;i++)
		for(int l=0;l<2;l++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++){
					if(k && j)continue;//no two consecutive buildings
					ll extra = t(dp[seg1][i][j] * dp[seg2][k][l]);
					dp[dest][i][l] = t(dp[dest][i][l]+extra);
					sum[dest] = t(sum[dest] + extra);
				}
}

int main(){
	//precompute fibonacci for single line road on 2's powers
	dp[0][0][0] = dp[0][1][1] = 1;
	int used;//entries used in dp[] array
	for(used=1;(1LL<<used)<=N;used++){//only necessary powers of 2 (<=N)
		//combine segment dp[used-1] with dp[used-1] to double the length
		combine(used,used-1,used-1);
		printf("precompute for 2^%d = %8lld gives \t%lld\n",used,1LL<<used,sum[used]);
	}

	//solve for N
	int prevseg = -1;
	for(int i=0;(1LL<<i)<=N;i++)//combine all 2's powers that forms the N
		if(N & (1LL<<i))
			if(prevseg<0)
				prevseg = i;
			else 
				combine(used,i,prevseg), prevseg = used++;
	
	ll ans = (prevseg<0LL) ? 0LL : sum[prevseg];//in case N==0
	printf("singleroad=%lld,\tdoubleroad=%lld\n",ans,t(ans*ans));
	return 0;
}

/*
H παράσταση 1LL<<k (ολίσθηση του 1, k φορές προς τα αριστερά) μας δίνει το 2^k.
Οπότε κάνοντας μια απαρίθμηση στις δυνάμεις του 2 (με τη χρήση του 1LL<<i στο for) βρίσκουμε αν μια δύναμη
χρειάζεται στην έκφραση του Ν (η συνθήκη N & (1LL<<i) θα είναι αληθής) ή όχι (συνθήκη ψευδής).

Μια λεπτομέρια στην υλοποίηση. Η combine αποθηκεύει αποτελέσματα μόνο στον πίνακα dp[] οπότε χρησιμοποιούμε 
τις πρώτες θέσεις του dp[] για τα precompute και τις επόμενες θέσεις για τη σύνθεση του Ν.
Η μεταβλητή used φροντίζει να μην ξαναχρησιμοποιήσουμε κατά λάθος κάποια θέση του dp[]
*/
Αν υπάρχουν απορίες, ρωτήστε άφοβα.
Αν βρείτε λάθη έκφρασης στο κείμενο, sorry αλλά μετά από κάποιο χρόνο δεν γίνεται άλλο edit! :D
Απάντηση