首页 > 其他分享 >2024牛客多校第九场 C.Change Matrix 欧拉反演

2024牛客多校第九场 C.Change Matrix 欧拉反演

时间:2024-08-22 21:19:43浏览次数:14  
标签:lfloor phi Matrix int sum 矩阵 多校 rfloor 反演

这题是欧拉反演的应用,之前没学过欧拉函数和欧拉反演,傻傻对着 \(gcd(i,j)\) 不知道怎么化简。

首先对原来的矩阵进行转化,拆成 \(n\) 个小矩阵

因为\(gcd(i,j)= \sum_{x|i,x|j} \phi(x)\)

这是因为对于任意的正整数 \(n\) 都有 \(n=\sum_{d|n} \phi(d)\),证明见oiwiki:https://oi-wiki.org/math/number-theory/euler-totient/

那把 \(n\) 替换成 \(gcd(i,j)\) 就得到上面的式子。但这个式子只是对于 \(i,j\) 固定为某个值的情况,考虑枚举 \(i\) 从 \(1\) 到 \(n\) ,\(j\) 同理。得到:

\(\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}gcd(i,j)=\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}\sum_{c|i,c|j}\phi(c)\)

反演有一个常见套路就是把最后枚举的这个 \(c\) 提到前面来(这跟在莫比乌斯反演里经常把 \(d\) 提到前面来是一样的),所以调换求和顺序把式子改写成:

\(\sum_{c=1}^{c=n}\phi(c)\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}[c|i ][c|j]\)

(其中 \([c|i]\) 的意思是若 \(c\) 整除 \(i\) ,则该表达式的值为 \(1\) ,否则为 \(0\) )

观察到 $i \in [1,n] $ 时,满足 \([c|i]\) 的 \(i\) 共有 \(\lfloor n/c \rfloor\) 个,\(j\) 同理,所以还可以写成:

\(\sum_{c=1}^{c=n}\phi(c)*\lfloor n/c \rfloor*\lfloor n/c \rfloor\)

这个式子的含义是,对于每个 \(c\) ,它都对应了一个长和宽都为 \(\lfloor n/c \rfloor\) 的矩阵,且矩阵内每个元素的初始值都为 \(\phi(c)\) 。第 \(c\) 个矩阵的行列 \((i,j)\) 在原矩阵中对应的位置是 \((i*c,j*c)\) 。
比如当前第 \(c\) 个矩阵长这样(只描述下标,每个位置对应的权值都是 \(\phi(c)\) ):

\[\left[ \begin{matrix} 1,1 & 1,2 & 1,3 &...&1,\lfloor n/c \rfloor\\ 2,1 & 2,2 & 2,3 &...&2,\lfloor n/c \rfloor\\ &...&\\ \lfloor n/c \rfloor,1 & \lfloor n/c \rfloor,2 & \lfloor n/c \rfloor,3 &...& \lfloor n/c \rfloor,\lfloor n/c \rfloor \end{matrix} \right] \]

则在原矩阵中它们对应的位置为:

\[\left[ \begin{matrix} c,c & c,2c & c,3c &... & c,\lfloor n/c \rfloor*c\\ 2c,c & 2c,2c & 2c,3c &...&2c,\lfloor n/c \rfloor*c\\ ... \\ \lfloor n/c \rfloor*c,c & \lfloor n/c \rfloor*c,2c & \lfloor n/c \rfloor*c,3c &... & \lfloor n/c \rfloor*c,\lfloor n/c \rfloor*c \end{matrix} \right] \]

显然一共有 \(n\) 个矩阵 ( \(c \in [1,n]\) ),所有矩阵的元素和加起来就等于我们要求的值。转化的意义在于把原本的大矩阵拆成了若干个小矩阵,每个小矩阵的 \(\phi()\) 都相等,原本矩阵里某个位置(i,j)的值就等于它出现过的小矩阵在该位置累加的和,有点像分层。

再放个雨巨的图方便大家理解:

\(c=1\) 时

\(c=2\) 时

\(c=3\)时

\(c=4\)时

接下来考虑每次操作对这些矩阵的影响

行和列是等价的,故只考虑行。

回到之前的这个式子:

\(\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}[c|i ][c|j]\) ,当改动第 \(x\) 行时,影响的是 \(i=x\) 和所有满足 \(c|x\) 的 \(c\) (暂且先不考虑后面的 \(j\) )。所以对于 \(x\) 的每个因数 \(c\) , 第 \(c\) 个矩阵都会受影响。

具体是什么影响?观察图可知,在原来的大矩阵里改一行时,对应的小矩阵也是改一整行。只不过对于第 \(c\) 个矩阵来说,\(x\) 在这个矩阵里对应的是第 \(x/c\) 行,所以改的是第 \(x/c\) 行(这里有点难解释,多悟一悟)。

那我们可以用数组 \(r[c][i]\) 表示第 \(c\) 个矩阵第 \(i\) 行的系数,进行 \(R \ x \ y\) 操作时就是:
r[c][x/c]*=y

答案 \(ans=\sum_{c=1}^{c=n}\phi(c) *(\ \sum r(i,j)\ )*(\ \sum c(i,j)\ )\) ,每次修改时减去原来的贡献,进行修改,再加上新的贡献,具体细节见代码。

$ code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int maxn = 100005;
int phi[maxn];
int prime[maxn], cnt;
bool vist[maxn + 1];
void Euler(int n){
	phi[1] = 1;
	for (int i = 2; i <= n; i ++){
		if (!vist[i]) prime[++ cnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= cnt && i * prime[j] <= n; j ++){
			vist[i * prime[j]] = true;
			if (i % prime[j] != 0) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			else {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
}
int n,q;
int sumR[maxn],sumC[maxn];
vector<int>r[maxn],c[maxn];// 第i个矩阵的第j行系数和第i个矩阵的第j列系数
void solve(){
	cin>>n>>q;
	for(int i=0;i<=n;i++) r[i].clear(),c[i].clear();
	int ans=0;
	for(int i=1;i<=n;i++){
		r[i].push_back(0);
		c[i].push_back(0);
		sumR[i]=sumC[i]=0;
		for(int j=1;j<=n/i;j++)
			r[i].push_back(1),c[i].push_back(1),// 最开始系数都为1
			sumR[i]++,sumC[i]++;//sumR[i]表示第i个矩阵的行系数和
	}
	for(int i=1;i<=n;i++){
		ans+=phi[i]*(n/i)%mod*(n/i)%mod;//初始的答案
		ans%=mod;
	}

	while(q--){
		char op;cin>>op;
		if(op=='R'){
			int x,y;cin>>x>>y;
			y%=mod;
			for(int i=1;i*i<=x;i++){
				// 处理第i个矩阵
				if(x%i) continue;
				// 减去原来的贡献
				ans-=((phi[i]*r[i][x/i]%mod)*sumC[i])%mod;
				ans=(ans+mod)%mod;
				sumR[i]-=r[i][x/i];
				sumR[i]=(sumR[i]+mod)%mod;
				// 修改r[][]和sumR[]
				r[i][x/i]=r[i][x/i]*y%mod;
				sumR[i]+=r[i][x/i];
				sumR[i]%=mod;
				ans+=((phi[i]*r[i][x/i]%mod)*sumC[i])%mod;
				ans%=mod;
				
				// 处理x/i
				if(i*i!=x){
					int j=x/i;
					ans-=((phi[j]*r[j][x/j]%mod)*sumC[j])%mod;
					ans=(ans+mod)%mod;
					sumR[j]-=r[j][x/j];
					sumR[j]=(sumR[j]+mod)%mod;
					// update
					r[j][x/j]=r[j][x/j]*y%mod;
					sumR[j]+=r[j][x/j];
					sumR[j]%=mod;
					ans+=((phi[j]*r[j][x/j]%mod)*sumC[j])%mod;
					ans%=mod;
				}
			}
		}
		else {
			// 列同理
			int x,y;cin>>x>>y;
			y%=mod;
			for(int i=1;i*i<=x;i++){
				// 处理第i个矩阵
				if(x%i) continue;
				// change
				ans-=((phi[i]*c[i][x/i]%mod)*sumR[i])%mod;
				ans=(ans+mod)%mod;
				sumC[i]-=c[i][x/i];
				sumC[i]=(sumC[i]+mod)%mod;
				// update
				c[i][x/i]=c[i][x/i]*y%mod;
				sumC[i]+=c[i][x/i];
				sumC[i]%=mod;
				ans+=((phi[i]*c[i][x/i]%mod)*sumR[i])%mod;
				ans%=mod;
				
				if(i*i!=x){
					int j=x/i;
					ans-=((phi[j]*c[j][x/j]%mod)*sumR[j])%mod;
					ans=(ans+mod)%mod;
					sumC[j]-=c[j][x/j];
					sumC[j]=(sumC[j]+mod)%mod;
					// update
					c[j][x/j]=c[j][x/j]*y%mod;
					sumC[j]+=c[j][x/j];
					sumC[j]%=mod;
					ans+=((phi[j]*c[j][x/j]%mod)*sumR[j])%mod;
					ans%=mod;
				}
			}
		}
		cout<<ans<<"\n";
	}
}
signed main(){
	freopen("1.in","r",stdin);
	freopen("mycode.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Euler(100000);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

标签:lfloor,phi,Matrix,int,sum,矩阵,多校,rfloor,反演
From: https://www.cnblogs.com/liyishui2003/p/18374788

相关文章

  • 2024杭电多校第10场
    101002scenery(hdu7542)由于\(l\)序列不增、\(r\)序列不降,每处景色的拍摄安排在可选时间的开始/结束位置显然是最优的。设\(dp[i][j]\)表示(从后往前)考虑到第\(i\)处景色、可选时间从\(j\)开始的最晚结束位置,则转移方程:\(dp[i][max(l_i,j)+t_i]=max(dp[i][max(......
  • 题解:CF1986B Matrix Stabilization
    洛谷传送门题意一个\(n\timesm\)的矩阵,依次进行以下操作:从\((1,1)\)开始遍历矩阵,找到最小的\((i,j)\)满足\(a{i,j}\)的值严格大于其所有相邻(四联通)单元格的值,如果没有则退出将1操作找到的\(a_{i,j}-1\)返回1操作求最后的矩阵。思路模拟,我们按照题目所说,从......
  • 2024牛客多校第10场
    10Bstd::pair(B)模拟题,没什么难度,就是有点恶心。题解提到的二叉树做法赛时也想过,但写着不太顺手就放弃了,转而写了个类似括号匹配的解法。for(inti=1;i<=n;i++){strings;cin>>c[i]>>s;mp[s]=i;}while(q--){......
  • 2024杭电多校第9场
    91001树异或价值(hdu7529)对价值定义式进行转化,\((a_i\oplusa_j)\timeslca(a_i,a_j)\)可视为\(a_i,a_j\)的所有祖先下\(\suma_i\oplusa_j\),数组\(a\)总价值即各节点子树中任意两个子节点的异或之和。由按位异或的性质,不同二进制位之间答案互不影响,可简化考虑最低位即......
  • 反演(2)
    CP4反演与共轴圆系还是有很大关联的。我们说,共轴圆系反演后还是共轴圆系,理由如下:对于有两个交点的共轴圆系,反演后的所有圆还是过这两个点(的对应点),所以还是共轴圆系对于切于某点的共轴圆系,由反演的保相切,它们依旧相切与一点对于无交点的共轴圆系,我们找到与它共轭的共轴圆......
  • 反演(1)
    反演是一种几何变换。在给出它的具体变换前,需要明确几个概念:直线是一种退化的圆,我们将直线与圆统称为广义圆所有直线交于一个点,即无穷远点\(P_\infty\)需要指出的是,反演中所述的无穷远点只有一个,这与射影几何中无穷个的无穷远点有一定区别上述的定义可以给出广义圆的相......
  • 2024牛客多校第9场
    9BBreakSequence(B)似乎不止一次遇到线段树优化dp了,但仍然没做出来()\(dp[i]\)表示到\(i\)位置为止、将序列分成若干段的情况总数,一个显而易见的\(n^2\)做法是从\(1\)到\(i-1\)枚举\(j\),若\(j+1\)至\(i\)为合法区间,则有\(dp[i]=\sum\limitsdp[j]\).假......
  • 2024杭电多校第九场
    1007简单博弈,队友做的#include<bits/stdc++.h>usingnamespacestd;constintN=2e5;intn,a[N+5],b[N+5],A,B;boolvis[N+5];inlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch==......
  • 2024杭电多校第十场 1002树上询问(题解)
    题意给一棵树,每个节点有一个权值,并且权值是一个排列。接下来有多次操作,每次操作要么是交换两个节点权值,要么是询问一个权值区间\([L,R]\),判断是否存在树上的一个路径,使得路径上的权值恰好都在这个区间里分析由于询问的是树上的一个路径,联想到了树上莫队中对路径的处理。这里......
  • 2024牛客暑期多校训练营10
    Preface最后一场牛客多校了,本来感觉可以来个完美谢幕的结果最后2h和祁神双开双卡本来开局就因为大雨导致晚开+浑身湿透,中间一直冷的发抖硬是撑了下来J题写法因为常数问题一直卡着十连重测;而C题因为有概率为\(0\)的情况需要繁琐的判断,最后两个题都没过赛后我用priority......