Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define vi vector<int>
- #define vll vector<ll>
- #define ll long long
- #define pb push_back
- #define eb emplace_back
- #define mp make_pair
- #define ii pair<int,int>
- #define ff first
- #define ss second
- #define PRIMO 1000000007
- int n;
- int tb[1000000];
- int mymod(int a, int b) {
- if (a == 0 || b == 0) {
- return 0;
- }
- if (a == 1) {
- return b;
- }
- if (b == 1) {
- return a;
- }
- int aux = mymod(a, b/2);
- if ((b & 1) == 0) {
- return (aux+aux) % PRIMO;
- } else {
- return (aux + (aux+aux) % PRIMO) % PRIMO;
- }
- }
- int dp(int n) {
- if (n == 0) return 1;
- if (n == 1) return 0;
- if (tb[n] != -1) return tb[n];
- return tb[n] = mymod( (dp(n-1) + dp(n-2)) % PRIMO, n-1);
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- memset(tb, -1, sizeof(tb));
- cin >> n;
- int ans = dp(n);
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement