problem

題目標(biāo)題-最大值
現(xiàn)有一個(gè)長度為 nn 的序列 a_1,a_2,\cdots,a_na
1
?
,a
2
?
,?,a
n
?
。記 mx(a)mx(a) 為整個(gè)序列 aa 的最大值，即 mx(a)=\max(a_1,a_2,\cdots ,a_n)mx(a)=max(a
1
?
,a
2
?
,?,a
n
?
)。

對于一個(gè)序列 aa，記其權(quán)值 f(a)f(a) 為取得整個(gè)序列最大值的位置數(shù)量，即 \sum_{i=1}^n[a_i=mx(a)]∑
i=1
n
?
[a
i
?
=mx(a)]。其中 [A][A] 表示若 AA 為真，則其值為 11，否則為 00。

度度熊想知道滿足以下條件的所有不同序列的權(quán)值之和：

1.序列的長度為 nn。
2.對于所有的 a_ia
i
?
(1\le i \le n1≤i≤n)，滿足 a_ia
i
?
為整數(shù)，且 1\le a_i\le m1≤a
i
?
≤m。

由于答案可能很大，你只需要輸出答案對 998244353998244353 取模后的結(jié)果。

格式
輸入格式：
共一行，兩個(gè)整數(shù) n,mn,m (1\le n\times m\le10^{12}1≤n×m≤10
12
)，意義如上所述。

輸出格式：
共一行一個(gè)整數(shù)，表示答案對 998244353998244353 取模后的結(jié)果。

樣例 1
輸入：
4 3
輸出：
144
說明：

solution

• <1e7時(shí)套公式。$n{\sum }_{i=1}^m{i}^{n?1}$
• >1e7時(shí)套板子：https://www.cnblogs.com/Pro-king/p/10664390.html
• 兩題無罰時(shí)最后一小時(shí)前簽上道就可以拿到衣服。

#include<bits/stdc++.h> typedef long long LL; #define rep(i,x,y) for(auto i=(x);i<=(y);++i) #define F(i,a,b) for (LL i = a; i <= b; i ++) #define G(i,a,b) for (LL i = a; i >= b; i --) #define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) const LL Mo = 998244353, M = 1e6 + 10; const LL mod=998244353; using namespace std;LL pow2(LL a,LL b){LL r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod;b>>=1;}return r%mod;} LL pows(LL a, LL x) { if(x==0)return 1; LL t = pows(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; } LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; } LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; }else{LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r; }} void exgcd(LL a, LL b, LL &d, LL &x, LL & y, LL mod) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, mod); y -= x * (a / b); } } LL inv(LL a, LL mod) { LL d=0, x=0, y=0; exgcd(a, mod, d, x, y, mod); return d == 1 ? (x + mod) % mod : -1; }LL l, r, k, m, y[M], z[M], jc[M], suf[M], pre[M]; bool bz[M];void Init() {y[1] = 1, m = k + 2;F(i, 2, m) {if (!bz[i])z[++ z[0]] = i, y[i] = pows(i, k);F(j, 1, z[0]) {if (z[j] * i > m) break;bz[z[j] * i] = 1;y[z[j] * i] = (1ll * y[z[j]] * y[i]) % Mo;if (i % z[j] == 0) break;}}F(i, 2, m)y[i] = (y[i - 1] + y[i]) % Mo;jc[0] = 1;F(i, 1, m)jc[i] = 1ll * jc[i - 1] * i % Mo;jc[m] = pows(jc[m], Mo - 2);G(i, m - 1, 1)jc[i] = 1ll * jc[i + 1] * (i + 1) % Mo; } LL Solve(LL n) {pre[0] = suf[m + 1] = 1;F(i, 1, m)pre[i] = 1ll * pre[i - 1] * (n - i) % Mo;G(i, m, 1)suf[i] = 1ll * suf[i + 1] * (n - i) % Mo;LL Ans = 0;F(i, 1, m)Ans = (Ans + 1ll * y[i] * pre[i - 1] % Mo * suf[i + 1] % Mo * (((k-i+2)&1) ? (-1) : 1) * jc[i - 1] % Mo * jc[k + 2 - i] % Mo) % Mo;return Ans; }int main() {LL nn,mm,ans; cin>>nn>>mm;if(mm<1e7){LL x=nn-1;rep(i,1,mm)ans=(ans+pow2(i,x))%mod;ans=ans*nn%mod;cout<<(ans+mod)%mod<<"\n";return 0;}r=mm,k=nn-1;Init();cout<<(Solve(r)*nn%Mo+Mo)%Mo;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2022百度之星程序设计大赛 - 复赛 1003 最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。