TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P7375
  • 問題
  • P7375Diamond Rush
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    問題説明

    nodgd造了一个傻逼dp题,题目是这样的

    有一个n*n的网格图,你初始时在(1,1),要走到(n,n),只能往右和往下走,每走到一个点会获得$ (n^{2})^{a_{i,j}} $的权值

    求最大权值和

    由于wangdy AKIOI,答案过大,请对1e9+7取模后输出

    由于nodgd仍然觉得这道题跟deaf一样傻逼,所以他又加了一条限制,钦定有一个矩形区域不能经过

    为了展示你有快速回答的超能力,nodgd会进行q次询问,每次给出一个矩形区域

    由于nodgd TQL 他保证一定有至少一条路径可以从(1,1)到(n,n)

    入力形式

    第一行一个整数T表示数据组数

    对于每组数据

    第一行是两个数n和q

    接下来n行每行n个数

    第i行第j列的数表示$ a_{i,j} $

    接下来q行每行四个数xl,xr,yl,yr表示一个询问,

    求当所有满足$ xl \leq i \leq xr $且 $ yl \leq j \leq yr$的点(i,j)不能被经过时的最大答案

    出力形式

    对于每个询问输出一个数表示答案对1e9+7取模的结果

    サンプル入力

    1
    2 2
    2 3
    1 4
    1 1 2 2
    2 2 1 1

    サンプル出力

    276
    336

    ヒント

    T<=5 n<=400 q<=200000


    ソース  HDU 2020 Multi-University Training Contest 2