Educational Codeforces Round 98 (Rated for Div. 2) D. Radio Towers

Educational Codeforces Round 98 (Rated for Div. 2) D. Radio Towers

题目链接

There are n+2 towns located on a coordinate line, numbered from 0 to n+1. The i-th town is located at the point i.

You build a radio tower in each of the towns 1,2,…,n with probability 12 (these events are independent). After that, you want to set the signal power on each tower to some integer from 1 to n (signal powers are not necessarily the same, but also not necessarily different). The signal from a tower located in a town i with signal power p reaches every city c such that |c−i|<p.

After building the towers, you want to choose signal powers in such a way that:

  • towns 0 and n+1 don’t get any signal from the radio towers;
  • towns 1,2,…,n get signal from exactly one radio tower each.

For example, if n=5, and you have built the towers in towns 2, 4 and 5, you may set the signal power of the tower in town 2 to 2, and the signal power of the towers in towns 4 and 5 to 1. That way, towns 0 and n+1 don’t get the signal from any tower, towns 1, 2 and 3 get the signal from the tower in town 2, town 4 gets the signal from the tower in town 4, and town 5 gets the signal from the tower in town 5.

Calculate the probability that, after building the towers, you will have a way to set signal powers to meet all constraints.

Input

The first (and only) line of the input contains one integer n (1≤n≤2⋅105).

Output

Print one integer — the probability that there will be a way to set signal powers so that all constraints are met, taken modulo 998244353.

Formally, the probability can be expressed as an irreducible fraction xy. You have to print the value of x⋅y−1mod998244353, where y−1 is an integer such that y⋅y−1mod998244353=1.

Examples

input

2

output

748683265

input

3

output

748683265

input

5

output

842268673

input

200000

output

202370013

简单规律题~
分子就是斐波那契数列,分母就是 2 2 2 的次幂,分子乘分母的逆元即可,AC代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll mod=998244353;
ll a[N],n;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
int main()
{
    a[0]=1,a[1]=1;
    for(int i=2;i<N;i++) a[i]=(a[i-1]+a[i-2])%mod;
    cin>>n;
    cout<<a[n-1]*power(power(2,n),mod-2)%mod;
    return 0;
}
上一篇:《单词的减法》state1~state17(第二遍学习记录)


下一篇:《单词的减法》state1~state17(200p)