COFO::1452D Radio Towers

• Link : COFO::1452D

Problem

• level : 1600
• tag : combinatorics, dp, math
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit : 120
• Fermat’s little theorem

Point

• There are n + 2 towns
• You can decide creating a tower on town i or not
• And every tower has signal power value
  • If there’s tower on position i and the power is p, every city c can be reached by signal if satisfy below equation

  • c - i

    < p

• All towns should be under exactly one signal
• Find the probability
  • print the x /y

Design

• First of all, we need to the ways to meet the requirement
  • How many ways exists that covers all towns
• The thing is that there’s something to notice about power
  • If power value is 1, it can cover only town i itself
  • If power value is 2, it can cover towns i-1, i, i+1
  • If power value is 3, it can cover towns i-2, i-1, i, i+1, i+2
  • …
• As you can see, the covered towns will be always odd number
• Now we notice that, we need to make sum as n by adding odd numbers
  • And it can be solved with dp
  • dp[1] = 1; // {1}
  • dp[2] = 1; // {1, 1}
  • dp[3] = 2; // {1, 1, 1}, {3}
  • dp[4] = 3; // {1, 1, 1, 1}, {1, 3}, {3, 1}
  • …
• Now we know how many ways exists
• Also, we know that every possbile ways will be ‘2^n’
  • Because, each town can decide wether building a tower or not
• Then we need to find answer as dp[n] / (2^n)
• But we have to use modulo, so 2^n should be chaanged numerator, cuz it’s currently denominator
• We can do that with ‘fermat’s little theorem since we need to calculate with modulo
  • With prime p and integer a, a^p = a (mod p)
  • With prime p and integer a, and they are in disjoint relation, a^(p-1) = 1(mod p)
• So, I would use the first equation
  • When a is equal to 2^n,
  • (2^n)^p = 2^n (mod p)
  • 2^(np) = 2^n ( mod p )
    • Then we devide with ‘2^(2n)’
  • 2^(np - 2n) = 1/(2^n) (mod p)
  • 2^n(p - 2) = 1 / (2^n) (mod p)
  • Since we wanted to change 1/2^n into numerator it can be swapped as 2^n(p - 2)
  • Current p is 99824353
  • So, 2^n(99824351)
• In a nutshell,
  • dp[n] / 2^n changed as dp[n] * 2^n(99824351)
• Also, we need to use fast pow way

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
const ll MOD = 998244353;

ll mul(ll x, ll y){ return (x * y) % MOD; }
ll binpow(ll x, ll y) {
    ll ret = 1;
    while(y > 0) {
        if (y % 2 == 1) ret = mul(ret, x);
        x = mul(x, x);
        y /= 2;
    }
    return ret;
}
ll divide(ll x, ll y) {
    return mul(x, binpow(y, MOD - 2));
}
void solve() {
    int n; cin >> n;
    vector<ll> dp(n + 1, 0);
    // dp[i] : 홀수의 합이 i 가 되게 하는 경우의 수
    dp[1] = 1; // 1
    dp[2] = 1; // 1 1
    dp[3] = 2; // 1 1 1, 3
    dp[4] = 3; // {1, 1, 1, 1}, {1, 3}, {3, 1}
    // ...
    for(int i = 2; i <= n; i++) dp[i] = (dp[i-1] + dp[i-2]) %MOD;
    
    ll a = dp[n], b = binpow(2, n);
    cout << divide(a, b) << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}