WTOFK3 - Editorial

editorial
, ,
1

PROBLEM LINK:

Problem Link

DIFFICULTY:

MEDIUM

PREREQUISITES:

Math, Combinatorics.

ALGORITHMIC STEPS:

Analyze four cases:

  1. s = 1 or s > k, the answer is n^k.
  2. s = k, the answer is n^(k + 1) / 2.
  3. s mod 2 = 1, any string like abababab… is ok, so the answer is n^2.
  4. s mod 2 = 0, all symbols coincide and the answer is n.

EXPLANATION:

STEP 1. If s==1 then the answer is all possible strings. That is n^k.
        If s>k. There are 0 substrings of length s.
        All of them are palindromes because Any statement about empty set is truth.
        (MOST YOU MIGHT HAVE MISSED THIS POINT :) )
 STEP 2. The most simple observation says, If s==k then answer is simply n^(k+1)/2.
OTHER STEPS:
    Let's look at the case when s%2 == 1 Let a = an arbitrary character from "n" possible characters. 
    b = an arbitrary character other than "a" from "n" possible characters.

    If s is odd, a substring whose length is s out of following string is always a palindrome. 
    String : abababababa Substring s=3 => aba or bab s=5 => ababa or babab ... you see the pattern. So we have (n * (n-1)) possible patterns. Now, also remember that a string consisting of same characters are also allowed. string : aaaaaaa substring s=3 =>aaa s=5 => aaaaa And we have "n" number of such strings.

    So, answer is n*(n-1) + n = n*(n-1+1) = n*n

    Let's see what happens when s is even. If s is even, only allowed strings are the ones that consist of same characters. There are n such strings. 
    So answer for (s%2 == 0) is n.

SOLUTIONS:

Solution 
    #include<bits/stdc++.h>
    #define int long long int
    #define pb push_back
    #define F first
    #define S second
    #define N 100005
    const int mod = 1e9 + 7;
    using namespace std;
    int qmi(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) res = (long long)res * a % mod;
            a = (long long)a * a % mod;
            b >>= 1;
        }
        return res;
    }
    void solve() {
        int t=1;
        while (t--) {
            int k, n, s;
            cin >> k >> n >> s;
            if (s <= 0) {
                puts("0");
            } else if (s == 1 or s > k) {
                cout << qmi(n, k) % mod << endl;
            } else if (s == k) {
                cout << qmi(n, (k + 1) / 2) % mod << endl;
            } else if (s & 1) {
                cout << n*n % mod << endl;
            } else {
                cout << n % mod << endl;
            }
        }
        return;
    }
    int32_t main() {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        solve();
        return 0;
    }