33OJ
登录 注册

#P17784. 山田凉不是罪过

山田凉不是罪过

背景

『個性捨てたら死んでるのと一緒だよ』

题目描述

你在做一道 T2,太难了,于是你发到了网上有偿寻求帮助,于是凉来帮你了。

凉写了一个很牛的随机化代码,使得对于任意一个测试点,其均有 12\frac{1}{2} 的概率输出正确答案。但是这道题开启了子任务捆绑,所以你最终获得了 00 分的好成绩。

于是凉并没有得到报酬。无聊的凉好奇,怎样设计捆绑方案可以使得她的代码的期望总得分最大。

具体地,该题有 nn 个测试点,kk 个子任务,其中第 ii 个子任务的分值为 aia_i,你需要给每个子任务分配测试点数量,满足任何子任务都有正整数个测试点且测试点数之和恰为 nn,仅当同时通过一个子任务内的所有测试点时你的代码才会得到该子任务的分数。

各测试点通过事件独立,保证在本题约束下最大期望得分模 998244353998244353 有意义。

输入格式

第一行输入两个数 n,kn,k。

接下来一行输入 kk 个整数,第 ii 个数为 aia_i。

输出格式

第一行输出最大期望得分模 998244353998244353 意义下的结果。

第二行输出 kk 个数,第 ii 个数表示第 ii 个子任务内的测试点数量。

3 2
40 60
40
2 1

提示

对所有数据,满足 1≤n≤10181\le n\le 10^{18},1≤k≤1061\le k\le 10^6,k≤nk\le n,1≤ai≤1001\le a_i \le 100。


吃草吃草吃草ing……