首页 > 试题广场 >

病毒扩散

[编程题]病毒扩散

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛所在的城市有一种新型病毒开始扩散。在一个二维平面坐标系上，有一个感染者在 $\ (0,0)$ 的位置。从时刻 $\ 0$ 开始，每一个在 $\ (x,y)$ 的感染者都会让下一个时刻 $\ (x+1,y)$ ， $\ (x,y+1)$ 的感染者数量增加 $\ 1$ 。

上图展示了时刻 $\text{0}$ 和时刻 $\text{1}$ 病毒的扩散情况。在时刻 $\ 1$ ， $\text (0,0),(0,1),(1,0)$ 的感染者数量为 $\ 1$ 。在时刻 $\ 2$ ， $\ (0,0),(0,2),(2,0)$ 的感染者数量为 $\ 1$ ， $\ (0,1),(1,0),(1,1)$ 的感染者数量为 $\ 2$ 。

牛牛想知道，对于特殊的 $\ n$ 个点，在时刻 $\ t$ 感染者的数量。

输入描述:

第一行一个正整数，表示特殊点的数量。

接下来 行，每行三个非负整数 ，表示有一个特殊的点在 ，牛牛想知道在时刻  这个点有多少感染者。

输出描述:

对于每一个特殊的点，输出一行一个非负整数，表示在  时刻这个点的感染者数量，对 998244353 取模。

示例1

输入

输出

1
2
1

说明

见题目描述中的图片。

示例2

输入

输出

备注:

。

算法知识视频讲解

wenyisir

发表于 2020-04-24 22:09:20

数学方法推一下：我们枚举出t=1-5秒内的变化人数图当t=1时:11 1t=2时:12 21 2 1t=3s13 33 6 31 3 3 1t=4时14 46 12 64 12 1 展开全文

Lskkkno1

发表于 2020-04-24 22:02:12

病毒扩散题目描述题目讲的很清楚，这里就不加赘述了。正解考虑病毒扩散的组合意义，把它转化成从的方案数。一个点它在一秒内可以进行以下三种操作。不动（往上走（往右走至于这样为啥是对的，自己感性理解一下吧，直接讲也不太好讲。最后答案就是。 upd : 证明考虑暴力展开全文

段三园的小迷弟

发表于 2020-04-25 00:49:09

去博客看大图 #include<bits/stdc++.h> using namespace std; const int mod=998244353,T=5e3+10,N=1e3+10; typedef long&n 展开全文

19_hanhan

发表于 2020-04-25 19:34:53

这次比赛题目都超长，出题人太棒（hen）了。可以进链接看原题题目概要题目描述：一个二维平面，从左下角开始病毒扩散，每一个时刻每个感染点可以传上右两个点，使其+1。求某一点在某一时刻的感染数。输入描述：接下来n 行，每行三个非负整数xi 展开全文

孑然.1

发表于 2020-04-24 22:46:44

首先可以先写个程序看每个数，有啥规律代码： #include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const 展开全文

18duangduang

发表于 2020-04-25 12:13:50

大致题意:自行看题.分析:打表前10秒的情况，发现就是n次多项式系数问题.手推规律 t秒合法答案: C[t-x][y]*C[t][x]. 然后再判断一下没有感染的情况---( x+y>t ). #include<bits/stdc++.h> using namespace std; 展开全文

Meul

发表于 2020-05-01 14:48:45

Question 在一个二维平面坐标系上，有一个感染者在的位置。从时刻开始，每一个在的感染者都会让下一个时刻，的感染者数量增加。 Solution 比赛的时候是打表+OEIS找规律出来的结果。下面讲正解:官方题解里说然而我没有明白为什么可以这么转换，直到后来看了Lskkkno1写的证明才明白。我们展开全文

回归梦想

发表于 2020-04-29 21:39:12

链接：时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述牛牛想知道，对于特殊的 \ n n 个点，在时刻\ t t 感染者的数量。输入描述: 输出描述:对于每一个特殊的点，输出一行一个非负整数展开全文

问题信息

难度：

0条回答 0收藏 48浏览

病毒扩散

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

相关试题