# HAPPY NUMBERS - EDITORIAL

Practice

Author: Siddharth Jha
Tester: Siddharth Jha
Editorialist: Siddharth Jha

CAKEWALK

# PREREQUISITES:

Binary Exponentiation

# PROBLEM:

Find the Nth number of the sequence 1,3,7,15… as the numbers can be very large mod it with 998244353.

# QUICK EXPLANATION:

The Nth number of the sequence would be 2^N - 1

# SOLUTIONS:

Setter's Solution

//Siddharth Jha

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<ll, null_type, less, rb_tree_tag, tree_order_statistics_node_update> pbds;
//typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;

#define ll long long int
#define mod 998244353
#define inf 1e18
#define pb push_back
#define vi vector
#define vs vector
#define pii pair<ll,ll>
#define ump unordered_map
#define mp make_pair
#define pq_max priority_queue
#define pq_min priority_queue<ll,vi,greater >
#define all(n) n.begin(),n.end()
#define ff first
#define ss second
#define mid(l,r) (l+(r-l)/2)
#define bitc(n) __builtin_popcount(n)
#define SET(a) memset( a, -1, sizeof a )
#define CLR(a) memset( a, 0, sizeof a )
#define Pi 3.141592653589793
#define loop(i,a,b) for(int i=(a);i<=(b);i++)
#define looprev(i,a,b) for(int i=(a);i>=(b);i–)
#define _fast ios_base::sync_with_stdio(0); cin.tie(0);
#define iter(container,it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define log(args…) {string _s = #args; replace(_s.begin(), _s.end(), ‘,’, ’ '); stringstream _ss(_s); istream_iterator _it(_ss); err(_it, args); }
#define logarr(arr,a,b) for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
template T gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
template T lcm(T a, T b){return (a*(b/gcd(a,b)));}
vs tokenizer(string str,char ch) {std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;}

void err(istream_iterator it) {}
template<typename T, typename… Args>
void err(istream_iterator it, T a, Args… args) {
cout << *it << " = " << a << endl;
err(++it, args…);
}
ll binpow(ll a, ll b, ll m) {
a %= m;
ll res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}

void solve() {
ll n;
cin >> n;
cout << (binpow(2,n,mod) - 1 + mod)%mod << “\n”;
}

int main(int argc, char const *argv[]){
_fast
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
ll t; cin>>t;
while(t–){
solve();
}
return 0;
}