原题链接
2023 Hubei Provincial Collegiate Programming Contest
题解
K. Dice Game
原题题面
There are n+1 people playing a game with dice. Every person has a dice of m faces, each of which is equal-probability. Don't spend time wondering how this kind of dice can exist–You can image a generator which can generate numbers among [1,m] with equal-probability. At the beginning, each person throws his own dice, and the person with the smallest number of points loses. If more than one person throws the smallest number of dice at the same time, those who have thrown the smallest number of dice continue to throw dice until finally one person loses. Walk Alone doesn't like randomness. He uses magic to fix the points the first person throws every time. That is, the first person will always throw x points when the first person throws his dice, where x is pre-chosen by Walk Alone, while other n people still throw their dices randomly. Now Walk Alone wants to know for every x \in [1, m], the probability the first person will lose. To be more precise, you need to output the probability modulo 998\ 244\ 353. It can be proven that the probability can be presented as a fraction \frac{p}{q}. You need to output p\cdot q^{998\ 244\ 351} \bmod 998\ 244\ 353.
Input The only line of input contains two integers n, m (1 \le n\le 10^5, 2 \le m \le 10^5) denoting the number of people and the number of faces a dice is.
Output Output m integers in a line, the i-th number denoting the probability modulo 998\ 244\ 353 when x=i.
Example
Input
3 5
Output
1 577110017 873463809 982646785 0
中文翻译
有 n+1 个人在玩一个掷骰子的游戏。每个人都有一个 m 面的骰子，每个面都是等概率的。不要花时间去想这种骰子怎么会存在--你可以想象一个生成器，它可以在 [1,m] 中生成概率相等的数字。
一开始，每个人都掷出自己的骰子，点数最小的人输。如果有多人同时掷出最小点数的骰子，则掷出最小点数的人继续掷骰子，直到最后一人输为止。
独行侠不喜欢随机性。他用魔法固定了第一个人每次掷出的点数。也就是说，当第一个人掷骰子时，他总是会掷出 x 点数，其中 x 是 "独步天下 "事先选择好的，而其他 n 人仍然是随机掷骰子。
现在，"独步天下 "想知道每 x \in [1, m] 个骰子中，第一个人输的概率是多少。
更精确地说，你需要输出模数为 998\ 244\ 353 的概率。可以证明概率可以用分数 \frac{p}{q} 表示。您需要输出 p\cdot q^{998\ 244\ 351} \bmod 998\ 244\ 353 。
输入
唯一的一行输入包含两个整数 n, m ( 1 \le n\le 10^5 , 2 \le m \le 10^5 )，分别表示骰子的面数和人数。
输出
在一行中输出 m 个整数，其中 i 个数字表示 x=i 时的概率模为 998\ 244\ 353 。
思路
我们可以从 n 为 1 的时候开始考虑。假设第二个人投出的骰子大小为 x ，那么第一次就决出胜负，这时输的概率就是：
第一次投平局，然后第二次决出胜负，这时输的概率就是：
第一次、第二次都是平局，然后第三次决出胜负，这时输的概率就是：
连续 k-1 次投出平局，然后第 k 次决出胜负，这时输的概率就是：
上述情况情况相加，我们可以得到最多到第 k 次投骰子时第一个人输的概率为：
利用等比数列求和公式，我们可以得到以下公式：
所以当 k 趋向于无穷大时，第一个人相对于后面每个人而言，化简公式可以得到输的概率都是：
观察题目，我们不难发现对于第[2,n+1]个人而言，他们对答案的贡献是独立的。显然第一个人输的总概率为：
AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=998244353;
template <class T> T ksm(T x,T y){
T ans=1;
while (y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void solve(){
ll n,m;
cin>>n>>m;
ll key=ksm(m-1,mod-2);
cout<<1;
for(ll x=2;x<=m;++x){
if(x==m){
cout<<" 0";
}else{
cout<<" "<<ksm(m-x,n)%mod*ksm(key,n)%mod;
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
while(t--){
solve();
if(t)cout<<"\n";
}
return 0;
}
C. Darkness I
原题题面
Princess Celestia, is an Alicorn pony, the former co-ruler of Equestria alongside her younger sister Princess Luna. Princess Celestia raises the sun and governs Equestria, while Princess Luna raises the moon and oversees the realm of dreams. In early days, Luna felt overshadowed and ignored by the ponies of Equestria, who slept through her beautiful night sky. These negative emotions festered and eventually led her to be consumed by the darkness and power of the mythical creature known as Nightmare Moon. The darkness was spreading, and could be transformed into the following model: In an n\times m white 2D grid, there are several black grid points. Every second, all white points that are 4-neighbors of at least two black points will turn black. What is the minimum number of black points needed to turn the entire grid black in the end? 
Input The first line contains two integers, n and m (1\le n,m\le 10^5), representing the size of the grid.
Output Output a single integer representing the minimum number of black points needed.
Example
Input
2 2
Output
2
Note One of the minimal placement schemes of the sample is shown below. 
中文翻译
赛莱斯蒂亚公主是一匹艾丽科恩小马，曾与她的妹妹露娜公主共同统治着 Equestria。赛莱斯提亚公主掌管着太阳，统治着 Equestria，而露娜公主掌管着月亮，监管着梦境。
在早期，露娜觉得自己黯然失色，被艾奎斯特里亚的小马们忽视，他们在露娜美丽的夜空中沉睡。这些负面情绪不断发酵，最终导致她被黑暗和神话生物 "梦魇之月 "的力量所吞噬。
黑暗正在蔓延，可以转化成以下模型：
在一个 n\times m 白色二维网格中，有几个黑色网格点。
每隔一秒钟，所有与至少两个黑点相邻的白点都会变成黑点。
要使整个网格最终变黑，最少需要多少个黑点？
输入
第一行包含两个整数 n 和 m 。 (1\le n,m\le 10^5) 代表网格的大小。
输出
输出一个整数，代表所需的最小黑点数。
注
下图是样本的一个最小放置方案。
思路
我的思路是先假定 a<b 然后按对角线放一个黑点，最后多出的 b-a 条边尝试每次空一格白点来放黑点，对于多出部分是偶数的情况还要额外放一个黑点。特判一下 b 为 1 的情况。赛后队友盲猜了一个结论 (a+b+1)/2 竟然也过了。
AC代码
思路一
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a,b;
cin>>a>>b;
if(a>b)swap(a,b);
if(b==1){
cout<<1;
}else{
if(a==1||b==1){
cout<<b/2+1;
}else{
cout<<a+(b-a+1)/2;
}
}
return 0;
}
思路二
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<(a+b+1)/2;
return 0;
}
J. Expansion
原题题面
Applejack is a female Earth pony. She lives and works at Sweet Apple Acres with her grandmother Granny Smith, her older brother Big McIntosh, her younger sister Apple Bloom, and her dog Winona. She represents the element of honesty. Now Applejack is going to cultivate a row of wasteland, and it could be transformed into the following model: There are n cells in a row, each containing an integer a_i. Applejack start by cultivating cell number 1 and have 0 resources just before the end of time unit 1. Later, assuming Applejack have cultivated cells [1, x], at the beginning of each unit time, she can cultivate cell x+1, and at the end of each unit time, she obtain resources equal to the sum of integers on all cells she have cultivated. Applejack need to ensure that she always have non-negative resources(even after cultivating all cells). What is the minimum time needed to occupy all cells, or is it impossible? 
Input The first line contains an integer n (2\le n\le 10^5) which represents the length of the row of cells. The second line contains n integers a_i (-10^8\le a_i\le 10^8), representing the coefficients on the cells.
Output Output a single integer representing the minimum amount of time needed to occupy all cells, if a solution exists. Otherwise, output -1.
Examples
Input
3
1 -3 4
Output
4
Input
3
1 -4 2
Output
-1
Input
6
1 -2 1 -4 5 -1
Output
10
Note In the first example, Applejack can stay cell 1 until time 3, then she can cultivate cell 2 and cell 3 at time 3 and time 4. And at the end of time 1, time 2, time 3, time 4, she have 1, 2, 0, 2 resource correspondingly. In the second example, after cultivating all cells, the resources will eventually be negative.
中文翻译
苹果杰克是一匹雌性地球小马。她和祖母史密斯奶奶、哥哥大麦金托什、妹妹苹果布鲁姆以及小狗薇诺娜一起在甜苹果庄园生活和工作。她代表诚实。
现在小苹果要开垦一排荒地，它可以变成下面的模样：
一行有 n 个单元格，每个单元格包含一个整数 a_i 。苹果杰克从开垦编号为 1 的单元格开始，在时间单位 1 结束之前**有 0 个资源。
之后，假设小苹果培育了 [1, x] 个单元，在每个单位时间开始时，她可以培育 x+1 个单元，在每个单位时间结束时，她获得的资源等于她培育的所有单元上的整数之和。
小苹果需要确保她的资源总是不为负数（即使培育了所有细胞）。占据所有单元格所需的最短时间是多少？
输入
第一行包含一个整数 n 。 (2\le n\le 10^5) 表示单元格行的长度。
第二行包含 n 个整数 a_i 。 (-10^8\le a_i\le 10^8) ，表示单元格上的系数。
输出
如果存在解决方案，输出一个整数，表示占用所有单元格所需的最短时间。
否则，输出 -1 。
注
在第一个例子中，小苹果可以在 3 时间之前停留在 1 单元，然后她可以在 3 时间和 4 时间培养 2 单元和 3 单元。
而在时间 1 、时间 2 、时间 3 、时间 4 结束时，她相应地拥有 1, 2, 0, 2 资源。
在第二个例子中，培养完所有细胞后，资源最终将为负值。
思路
特判初始值或前缀和 pre[n] 为 0 的情况，尝试从1开始模拟到最后，每当目前的资源不够的时候，尝试在目前资源加的最多的地方多停留 need 个回合获取 need*maxx 个资源。倘若 maxx 的值为 0 ，说明无论如何都不能保证在无穷时间内资源数量非负，直接输出 -1 返回。
AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll a[(int)1e5+5];
ll pre[(int)1e5+5];
void solve(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
if(a[1]<0||pre[n]<0){
cout<<"-1";
}else{
ll ans=1;
ll now=a[1];
ll pos=1;
ll maxx=a[1];//不需要知道谁最大
while(pos<n){
// cout<<"pos:"<<pos<<"\n";
if(now+pre[pos+1]>=0){
++pos;
++ans;
now+=pre[pos];
maxx=max(maxx,pre[pos]);
}else{
if(!maxx){
cout<<-1;
return;
}
ll need=(abs(pre[pos+1]+now)-1)/maxx+1;
ans+=need;
now+=maxx*need;
}
}
cout<<ans;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
if(t)cout<<"\n";
}
return 0;
}
M. Different Billing
原题题面
Once upon a time, there was an onsite programming contest, which had attracted many teams to participate in. However, different teams had a different billing standard. In general, there were three types of teams: - Teams of Type A could participate in the contest for free. - Teams of Type B had to pay 1000 dollars for the expenses for board and lodging. - Teams of Type C had to pay 1000 dollars for the expenses for board and lodging and 1500 dollars for entry fee. Finally the contest was held successfully with x teams in total participating in, and the host had earned y dollars. However, the details about the number of teams of each type had vanished. Now Walk Alone wants to restore the details using x and y.
Input The only line of input contains two integers x and y (0 \le x \le 10^6, 0 \le y \le 10^9), denoting the number of teams in total and the total amount of money the host had earned.
Output If there's a way to construct the number three types of teams satisfying the condition above, output three integers A,B,C to denote the number of teams of type A, B and C. You need to guarantee that 0 \le A, B, C. If there are multiple ways, output any of them. If there's no answer satisfying the condition above, output -1 instead.
Example
Input
800 1500000
Output
200 0 600
Input
0 0
Output
0 0 0
Input
500 100
Output
-1
Note
For the first sample test case you can also output 50\ 250\ 500, which can also satisfy the condition above.
For the second sample test case, there's nobody who needs to bill participating in the contest, so no money can be earned by the host.
For the third sample test case, the host cannot earn such little money. So output -1.
中文翻译
曾经有一次现场编程比赛，吸引了很多团队参加。不过，不同的团队有不同的计费标准。一般来说，有三种类型的团队：
- A 类团队可以免费参赛。
- B 类参赛队需支付 1000 美元的食宿费用。
- C 类参赛队需支付 1000 美元的食宿费和 1500 美元的报名费。
最后，比赛成功举行，共有 x 支队伍参赛，主办方获得了 y 美元的收入。但是，每种类型参赛队数量的详细信息却消失了。现在，"独步天下 "希望使用 x 和 y 来恢复这些细节。
输入
唯一的一行输入包含两个整数 x 和 y （ 0 \le x \le 10^6 , 0 \le y \le 10^9 ），分别表示参赛队伍总数和主持人赚取的总金额。
输出
如果有办法构造出满足上述条件的三类球队的数量，请输出三个整数 A,B,C 表示 A、B 和 C 三类球队的数量。如果有多种方法，请输出任意一种。
如果没有满足上述条件的答案，则输出 -1 。
注
对于第一个示例测试用例，也可以输出 50\ 250\ 500 ，这也能满足上述条件。
对于第二个示例测试用例，没有人需要付费参加比赛，因此主办方赚不到钱。
对于第三个示例测试用例，主持人不可能赚到这么少的钱。因此输出 -1 。
思路
由于 A 类队伍不收费，因而我们可以尝试直接最大化 C 类队伍的个数，只要特判一下 C 类队伍会不会多算一队的情况即可。
AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll x,y;
void solve(){
cin>>x>>y;
ll x3=y/2500;
y-=x3*2500;
ll x2=y/1000;
y-=x2*1000;
if(y){
y+=2500;
--x3;
ll tmp=y/1000;
y-=tmp*1000;
x2+=tmp;
if(y){
cout<<-1;
}else{
cout<<x-x2-x3<<" "<<x2<<" "<<x3;
}
}else{
cout<<x-x2-x3<<" "<<x2<<" "<<x3;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
if(t)cout<<"\n";
}
return 0;
}
