Your task is to calculate the number of arrays such that:
- each array contains $n$ elements;
- each element is an integer from $1$ to $m$;
- for each array, there is exactly one pair of equal elements;
- for each array $a$, there exists an index $i$ such that the array is strictly ascending before the $i$-th element and strictly descending after it (formally, it means that $a_j < a_{j + 1}$, if $j < i$, and $a_j > a_{j + 1}$, if $j \ge i$).
Input
The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 2 \cdot 10^5$).
Output
Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo $998244353$.
Examples
input
3 4
output
6
input
3 5
output
10
input
42 1337
output
806066790
input
100000 200000
output
707899035
Note
The arrays in the first example are:
- $[1, 2, 1]$;
- $[1, 3, 1]$;
- $[1, 4, 1]$;
- $[2, 3, 2]$;
- $[2, 4, 2]$;
- $[3, 4, 3]$.
Solution:
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=998244353; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head int n,m; ll ans=1,r=1; int main() { scanf("%d%d",&n,&m); if (n==2) { puts("0"); return 0; } for (int i=1;i<=m;i++) ans=ans*i%mod; for (int i=1;i<=n-1;i++) r=r*i%mod; for (int i=1;i<=m-n+1;i++) r=r*i%mod; ans=ans*powmod(r,mod-2)%mod*(n-2)%mod; ans=ans*powmod(2,n-3)%mod; printf("%lld\n",ans); }
Related posts:
Magic Trick
Chinese Remainder Theorem
Edge connectivity / Vertex connectivity
New Year and the Treasure Geolocation
Hongcow's Game
Game with Chips
Attack on Red Kingdom
Fibonacci-ish II
Nested Rubber Bands
Network Configuration
Awesome Substrings
NEKO's Maze Game
Smallest Word
Mysterious Crime
Paint the Numbers
Treap (Cartesian tree)
Integration by Simpson's formula
Array Shrinking
Happy Cactus
Cow and Snacks
Dynamic Programming on Broken Profile
Not Wool Sequences
Minimum-cost flow - Successive shortest path algorithm
Bathroom terminal
New Year and Conference
Travelling Through the Snow Queen's Kingdom
Bits And Pieces
Maximum Reduction
Finding a negative cycle in the graph
Invertation in Tournament
Cron
Bus Video System