N-Dimensional Grid ——线性逆元

2024-04-07 01:18
文章标签 线性 grid 逆元 dimensional

本文主要是介绍N-Dimensional Grid ——线性逆元,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

You are given an n-dimensional grid in which the dimensions of the grid are a1?×?a2?×?…?×?an. Each cell in the grid is represented as an n-tuple (x1,?x2,?…,?xn) (1?≤?xi?≤?ai).

Two cells are considered to be adjacent if the Manhattan Distance between them is equal to 1. The Manhattan Distance between two cells X(x1,?x2,?…,?xn) and Y(y1,?y2,?…,?yn) is equal to: |x1?-?y1|?+?|x2?-?y2|?+?…?+?|xn?-?yn|.

Your task is to count how many pairs of cells are adjacents. Can you? Two pairs of cells are considered the same if they include the same cells, i.e the pair (c1,?c2)is the same as (c2,?c1).

Input
The first line contains an integer T (1?≤?T?≤?100) specifying the number of test cases.

The first line of each test case contains an integer n (1?≤?n?≤?105), in which n is the number of dimensions of the grid. Then a line follows containing n integers a1,?…,?an (1?≤?ai?≤?105), in which ai is the size of the ith dimension.

The sum of n overall test cases does not exceed 6?×?106.

Output
For each test case, print a single line containing the number of pairs of adjacent cells modulo 109?+?7.

Example
Input
1
3
1 2 3
Output
7
Note
The absolute value |x| of a real number x is the non-negative value of x without regard to its sign. Namely, |x| = x for a positive x, |x| = ?-?x for a negative x (in which case ?-?x is positive), and |0| = 0. For example, the absolute value of 3 is 3, and the absolute value of ?-?3 is also 3. The absolute value of a number may be thought of as its distance from zero.

在比赛的时候连题意都没看懂,

结束之后听旁边的人说的,a[i]是约束条件,就是说样例之中不能出现大于123的点,211这种。

之后就好办了,我们可以发现曼哈顿距离为1的时候,必然是有两个数是相同的,另一个数有(n-1)

种组合,所以结果是(a-1)b*c+a(b-1)c+a*b(c-1);

但是一个一个算太麻烦了,所以可以用逆元=a*b*c*(a-1)/a;

然而每一次都算一遍逆元的话会t,所以需要一个东西叫做线性逆元,就是说在p之内的所有逆元

都可以算出来,公式是a[i]=(mod-mod/i)*a[mod%i]%mod;

a[1]=1;

#include<bits/stdc++.h>using namespace std;#define ll long long#define mod 1000000007ll a[100005];ll ny[100005];void init(){ny[1]=1;for(int i=2;i<=100000;i++)ny[i]=((mod-(mod/i))*ny[mod%i])%mod;}int main(){int t;scanf("%d",&t);init();while(t--){int n;scanf("%d",&n);ll ans=1,sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ans=(ans*a[i])%mod;}for(int i=1;i<=n;i++){sum=(sum+(ans*(a[i]-1)%mod*ny[a[i]])%mod)%mod;}printf("%lld\n",sum);}return 0;}

这篇关于N-Dimensional Grid ——线性逆元的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881304

相关文章

hdu4828(卡特兰数+逆元)

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列 下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n,其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32.................................. 但是这题的n太大了,所以要用到逆元,

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

✨机器学习笔记(二)—— 线性回归、代价函数、梯度下降

1️⃣线性回归(linear regression) f w , b ( x ) = w x + b f_{w,b}(x) = wx + b fw,b​(x)=wx+b 🎈A linear regression model predicting house prices: 如图是机器学习通过监督学习运用线性回归模型来预测房价的例子,当房屋大小为1250 f e e t 2 feet^

【高等代数笔记】线性空间(一到四)

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n

LibSVM学习(六)——easy.py和grid.py的使用

我们在“LibSVM学习(一)”中,讲到libSVM有一个tools文件夹,里面包含有四个python文件,是用来对参数优选的。其中,常用到的是easy.py和grid.py两个文件。其实,网上也有相应的说明,但很不系统,下面结合本人的经验,对使用方法做个说明。        这两个文件都要用python(可以在http://www.python.org上下载到,需要安装)和绘图工具gnup

带头结点的线性链表的基本操作

持续了好久,终于有了这篇博客,链表的操作需要借助图像模型进行反复学习,这里尽可能的整理并记录下自己的思考,以备后面复习,和大家分享。需要说明的是,我们从实际应用角度出发重新定义了线性表。 一. 定义 从上一篇文章可以看到,由于链表在空间的合理利用上和插入、删除时不需要移动等优点,因此在很多场合下,它是线性表的首选存储结构。然而,它也存在某些实现的缺点,如求线性表的长度时不如顺序存储结构的

浙大数据结构:02-线性结构4 Pop Sequence

这道题我们采用数组来模拟堆栈和队列。 简单说一下大致思路,我们用栈来存1234.....,队列来存输入的一组数据,栈与队列进行匹配,相同就pop 机翻 1、条件准备 stk是栈,que是队列。 tt指向的是栈中下标,front指向队头,rear指向队尾。 初始化栈顶为0,队头为0,队尾为-1 #include<iostream>using namespace std;#defi

深度学习与大模型第3课:线性回归模型的构建与训练

文章目录 使用Python实现线性回归:从基础到scikit-learn1. 环境准备2. 数据准备和可视化3. 使用numpy实现线性回归4. 使用模型进行预测5. 可视化预测结果6. 使用scikit-learn实现线性回归7. 梯度下降法8. 随机梯度下降和小批量梯度下降9. 比较不同的梯度下降方法总结 使用Python实现线性回归:从基础到scikit-learn 线性

C#中的各种画刷, PathGradientBrush、线性渐变(LinearGradientBrush)和径向渐变的区别

在C#中,画刷(Brush)是用来填充图形(如形状或文本)内部区域的对象。在.NET框架中,画刷是System.Drawing命名空间的一部分,通常用于GDI+绘图操作。以下是一些常用的画刷类型: SolidBrush:用于创建单色填充的画刷。HatchBrush:用于创建具有图案填充的画刷。TextureBrush:用于创建具有图像纹理填充的画刷。LinearGradientBrush:用于创