Bayraqlar (Həll təhlili)

Tutaq ki:

• f_r(n) — $n$ zolaqdan ibarət bayrağı qırmızı zolaqla başlayaraq boyamağın üsullarının sayı;

• f_w(n) — $n$ zolaqdan ibarət bayrağı ağ zolaqla başlayaraq boyamağın üsullarının sayı;

f_r(n) funksiyasının hesablanmasını nəzərdən keçirək:

• Əgər qırmızının ardından ağ zolaq qoyulsa, qalan n - 1 uzunluğundakı bayrağı f_w(n - 1) üsullarla boyamaq olar;

• Əgər qırmızının ardından mavi zolaq qoyulsa, mavinin ardından ağ zolaq olmalıdır. Bundan sonra qalan n - 2 uzunluğundakı bayrağı f_w(n - 2) üsullarla boyamaq olar;

Beləliklə, bərabərlik alırıq:

Oxşar fikir yürüdərək alırıq:

Birinci rekursiyanın başlanğıc şəraitləri açıqdır:

• fr(1) = 1: Qırmızı ilə başlayan bir zolaqlı bayraq yalnız bir şəkildə — $R$ — boyana bilər.

• fr(2) = 1: Əgər birinci zolaq qırmızıdırsa, ikincisi qırmızı ola bilməz və mavi ola bilməz (mavi qırmızı və ağ arasında olmalıdır), buna görə ikinci zolaq mütləq ağ olmalıdır. Yeganə variant — $RW$.

Eyni şəkildə

Hər iki funksiya — həm f_r(n) həm də f_w(n) Fibonacci ədədlərini təyin edir:

Bayrağın boyaması birinci zolaqdan başlayır. O ya qırmızı, ya da ağ ola bilər. Buna görə ümumi bayrağı boyamaq üsullarının sayı

Algoritmin həyata keçirilməsi

Konstantları elan edək.

#define MAX 1000001
#define MOD 1000000007

Fibonacci ədədlərini saxlamaq üçün $fib$ arrayini elan edək.

long long fib[MAX];

Giriş dəyəri $n$ oxuyuruq.

scanf("%d", &n);

$fib$ arrayini Fibonacci ədədləri ilə doldururuq.

fib[1] = 1; fib[2] = 1;
for (i = 3; i < MAX; i++) 
  fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;

Cavabı çıxarırıq.

printf("%lld\n", (2 * fib[n]) % MOD);