# PBinfo #1656 – UnuZero – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se consideră un şir format din N+2 cifre binare, care conţine cel puţin o cifră 1 şi cel puţin trei cifre 0; prima şi ultima cifră a şirului sunt 0.
Numim 1-secvenţă o succesiune formată numai din cifre 1, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră 0.

Corina construieşte un astfel de şir, în care numărul de cifre 1 ale fiecărei 1-secvenţe să fie cuprins între două numere naturale date, p şi q (p ≤ q). 

Cerința
Scrieţi un program care să determine un număr natural K, egal cu restul împărţirii la 666013 a numărului de şiruri distincte, de tipul celui construit de Corina.

Date de intrare
Fişierul de intrare unuzero.in conţine pe prima linie numărul natural N, iar pe cea de a doua linie numerele naturale p şi q ( p ≤ q ), separate printr-un spaţiu.

Date de ieșire
Fişierul de ieşire unuzero.out va conţine pe prima linie numărul natural K cerut.

Restricții și precizări

1 ≤ p ≤ q < N < 1.000.000
Pentru 20% din teste N ≤ 25, iar pentru alte 40% din teste 25 < N ≤ 1000.

Exemplu:
unuzero.in

5
2 3
unuzero.out

8
Explicație
0000110
0001100
0001110
0011000
0011100
0110000
0110110
0111000

## Cod sursă C++

```cpp
// O(n)
#include <fstream>
using namespace std;
int mod=666013,a,b;
int s[1000100],u[1000100],z[1000100],n;
int main()
{
	ifstream in("unuzero.in");
	ofstream out("unuzero.out");
	in>>n>>a>>b;
	z[0]=1;
	s[0]=1;
	for(int i=1;i<=n;++i)
	{
		z[i]=z[i-1]+u[i-1]; // daca punem 0
		z[i]%=mod;
		if(i-a>=0)
		{
			if(i-b-1>=0)
			{
				u[i]=s[i-a]-s[i-b-1];
			}
			else
			{
				u[i]=s[i-a];
			}
		}
		if(u[i]<0) u[i]+=mod;
		u[i]%=mod;
		s[i]=s[i-1]+z[i];
		s[i]%=mod;
	}
	out<<(z[n]+u[n]-1+(z[n]+u[n]-1<0?mod:0))%mod<<'\n';
	out.close();
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1656)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1656/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1656/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)