#P8733. [2024年7月福建集训]雪雀
[2024年7月福建集训]雪雀
雪雀(snowfinch)
题目描述
雪雀在一个 的网格草原上觅食,网格草原上的每个位置都有一个权值,一条路径的长度等于它经过的所有点的权值之和(包括起点和终点)。
每次可以移动到上下左右相邻的格子。雪雀希望按最短路觅食,同时,它希望对于任意满足 的有序点对 ,从 走到 恰好一次。
请你帮助雪雀求出,它总共要走多长的路。
输入格式
从标准输入读入。
第一行一个正整数。
接下来三行,每行 个正整数,表示每个位置的权值。权值按完整十进制整数读取,不依赖额外的数值上界。
输出格式
向标准输出写出。
输出一个整数表示答案,对 取模。
样例输入
3
1 1 1
1 100 1
1 1 1
样例输出
1808
数据范围与提示
对于 % 的数据,。 对于 % 的数据,。 对于 % 的数据,。 对于 % 的数据,。
本地编译标程
随题提供 exact_integer.h,与 std.cpp 放在同一目录,可用 C++17 联合编译。该辅助类只负责精确整数的加减、比较和取模,普通64位范围走快速分支,超出后使用任意精度。