E - Integer Sequence Fair

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

Integer Sequence Exhibition is taking place, where integer sequences are gathered in one place and evaluated. Here, every integer sequence of length NN consisting of integers between 11 and KK (inclusive) is evaluated and given an integer score between 11 and MM (inclusive).

Print the number, modulo 998244353998244353, of ways to give each of the evaluated sequences a score between 11 and MM.

Here, two ways are said to be different when there is an evaluated sequence A = (A_1, A_2, \ldots, A_N)A=(A1​,A2​,…,AN​) that is given different scores by the two ways.

Constraints

• 1 \leq N, K, M \leq 10^{18}1≤N,K,M≤1018
• NN, KK, and MM are integers.

---

Input

Input is given from Standard Input in the following format:

NN KK MM

Output

Print the number, modulo 998244353998244353, of ways to give each of the evaluated sequences a score between 11 and MM.

---

Sample Input 1 Copy

Copy

2 2 2

Sample Output 1 Copy

Copy

16

Four sequences are evaluated: (1, 1)(1,1), (1, 2)(1,2), (2, 1)(2,1), and (2, 2)(2,2). There are 1616 ways to give each of these sequences a score between 11 and 22, as follows.

• Give 11 to (1, 1)(1,1), 11 to (1, 2)(1,2), 11 to (2, 1)(2,1), and 11 to (2, 2)(2,2)
• Give 11 to (1, 1)(1,1), 11 to (1, 2)(1,2), 11 to (2, 1)(2,1), and 22 to (2, 2)(2,2)
• Give 11 to (1, 1)(1,1), 11 to (1, 2)(1,2), 22 to (2, 1)(2,1), and 11 to (2, 2)(2,2)
• Give 11 to (1, 1)(1,1), 11 to (1, 2)(1,2), 22 to (2, 1)(2,1), and 22 to (2, 2)(2,2)
• \cdots⋯
• Give 22 to (1, 1)(1,1), 22 to (1, 2)(1,2), 22 to (2, 1)(2,1), and 22 to (2, 2)(2,2)

Thus, we print 1616.

---

Sample Input 2 Copy

Copy

3 14 15926535

# include<iostream>
# include<iomanip>
# include<algorithm>
# include<map>
# include<vector>
# include<set>
# include<cstring>
# pragma optimize(2)
# define mod1 998244353
# define mod2 998244352
using namespace std;

typedef long long int ll;


ll qp2(ll base, ll pow)
{
    ll ans=1;

    while(pow)
    {
        if(pow&1)
            ans=ans*base%mod2;

        pow>>=1;

        base=base*base%mod2;

    }
    return ans;

}

ll qp1(ll base, ll pow)
{
    ll ans=1;

    while(pow)
    {
        if(pow&1)
            ans=ans*base%mod1;

        pow>>=1;

        base=base*base%mod1;

    }
    return ans;

}
int main ()
{

   ll n,k,m;

   cin>>n>>k>>m;


   if(m%998244353==0)
   {
       cout<<0;

       return 0;
   }
   else
   {
       ll now=qp2(k%(mod2),n);

       ll ans=qp1(m%(mod1),now);


       cout<<ans<<'\n';




   }


    return 0;

}

Sample Output 2 Copy

Copy

109718301

Be sure to print the count modulo 998244353998244353.

=========================================================================

费马小定理的应用

正整数 n , 当模数p是质数，且 gcd(n,p)==1时，n^(p-1)=1 (mod p)

本题答案显然是  ,显然会想到快速幂，但我们长做的快速幂，指数部分是无法进行取模操作的，而本题的指数一旦不取模，会立刻炸掉，所以考虑对指数进行一些操作

如果m与p不互质，又因为p是质数，故m一定是p的倍数，此时已知答案为0

如果m与p互质，那么，将k^n拆分成  x*(p-1) + mod ，左半部分答案是1，右半部分答案直接用快速幂就可以直接解决。