HBC230981[HEOI2013]SAO,数位dp,树形dp,动态规划George's Grass题解

把回忆走一遍算法基础篇 2023-11-21 20:50:01 56 0

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

0, there is no weed on the farm.. Each use of the mower completely removes weeds in a row or a column.George wonders how many units of weed he will remove.The answer might be very large, so please output the desired answer modulo

Besides George Plover's house stands a farm. The farm can be described as an ntimes m n×m matrix. The growth rate of weed in row i i and column j j is denoted as a_{ij} a ij . In this problem, two arrays {A_1, A_2, ..., A_n} {A 1 ,A 2 ,...,A n } and {B_1, B_2, ..., B_m} {B 1 ,B 2 ,...,B m } will be given. And for all 1leq ileq n 1≤i≤n, 1 leq jleq m 1≤j≤m , a_{ij}=A_i times B_j a ij =A i ×B j . The growth rate a_{ij} a ij indicates that the weed will grow a_{ij} a ij units every second. At the moment 0, there is no weed on the farm. George will use mower q q times, where the i i-th use occurs at the moment t_i t i . Each use of the mower completely removes weeds in a row or a column. George wonders how many units of weed he will remove. The answer might be very large, so please output the desired answer modulo 10^9+7 10 9 +7.