2022百度之星程序设计大赛 - 复赛 1003 最大值

举报
小哈里 发表于 2022/09/25 04:41:25 2022/09/25
【摘要】 problem 题目标题-最大值 现有一个长度为 nn 的序列 a_1,a_2,\cdots,a_na 1 ​ ,a 2 ​ ,⋯,a n ​ 。记 mx(a)mx(a) 为整个序列 aa 的最大值...

problem

在这里插入图片描述

题目标题-最大值
现有一个长度为 nn 的序列 a_1,a_2,\cdots,a_na
1

,a
2

,⋯,a
n

。记 mx(a)mx(a) 为整个序列 aa 的最大值,即 mx(a)=\max(a_1,a_2,\cdots ,a_n)mx(a)=max(a
1

,a
2

,⋯,a
n

)。

对于一个序列 aa,记其权值 f(a)f(a) 为取得整个序列最大值的位置数量,即 \sum_{i=1}^n[a_i=mx(a)]∑
i=1
n

[a
i

=mx(a)]。其中 [A][A] 表示若 AA 为真,则其值为 11,否则为 00。

度度熊想知道满足以下条件的所有不同序列的权值之和:

1.序列的长度为 nn。
2.对于所有的 a_ia
i

(1\le i \le n1≤i≤n),满足 a_ia
i

为整数,且 1\le a_i\le m1≤a
i

≤m。

由于答案可能很大,你只需要输出答案对 998244353998244353 取模后的结果。

格式
输入格式:
共一行,两个整数 n,mn,m (1\le n\times m\le10^{12}1≤n×m≤10
12
),意义如上所述。

输出格式:
共一行一个整数,表示答案对 998244353998244353 取模后的结果。

样例 1
输入:
4 3
输出:
144
说明:

solution

  • <1e7时套公式。 n ∑ i = 1 m i n − 1 n\sum_{i=1}^{m}i^{n-1} ni=1min1
  • >1e7时套板子:https://www.cnblogs.com/Pro-king/p/10664390.html
  • 两题无罚时最后一小时前签上道就可以拿到衣服。
#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;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/126909796

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200