首页 > 其他分享 >照亮数学的七道光芒 T1-4

照亮数学的七道光芒 T1-4

时间:2024-04-25 22:12:07浏览次数:20  
标签:frac sd2 int sum T1 七道 照亮 svd sd

照亮数学的七道光芒

勇气

对于第 \(k\) 次攻击,其攻击力为:

\[a_k=\frac{x^{2^k}}{2^{2^k-2}} \]

对于这个题,显然就是找最小的 \(k\) 使满足这个式子

\[\frac{x^{2^k}}{2^{2^k-2}}\geq 2^n \]

以 \(2\) 为底取对数,有

\[2^k\log_2x-(2^k-2) ≥ n \]

\[2^k ≥\frac{n-2}{\log_2x -1} \]

如果 \(x\geq 2^n\) 答案直接就是零,如果 \(x=2\) 而 \(n>2\) 则无解。

signed main()
{
    cin >> x >> n;
	if (x == 2 && n > 2) 
	{
		cout << "inf";
		return 0;
	} 
	else if (x == 2 && n == 2) 
	{
		cout << 1;
		return 0;
	} 
	else if (n == 1) 
	{
		cout << 0;
		return 0;
	}
	int times = (ceil)(n - 2) / (log2(x) - 1);
	int check = 1;
	if (check >= times)
	{
		cout << 0;
		return 0;
	}
	for (rint i = 1; ; i++)
	{
		check *= 2;
		if (check >= times) 
		{
			cout << i;
			return 0;
		}
	}
}

奉献

仔细读题寻找性质,当且仅当 \(\gcd(a,b)=1\) 时,它没有在之前被填写过

将朴素式子列出来:

\[\sum_{i=1}^n\sum_{j=1}^i(d_i\log_2d_i+\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}d_k)\times check(\gcd(i,j)) \]

其中 \(check(x)\) 为 bool 型,当且仅当 \(x=1\) 时为 \(1\),否则为 \(0\)。

将式子进行转化:

\[\sum_{i=1}^n(d_i\log_2d_i+\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}d_k)\sum_{j=1}^icheck(\gcd(i,j)) \]

即为:

\[\sum_{i=1}^n(d_i\log_2d_i+\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}d_k)\times\varphi(i) \]

这些东西我们都是会求的,这个题最后一个地方,在于 \(d_i\) 不能直接求,差分一下。

void init() 
{
	v[1] = phi[1] = 1;
	for (rint i = 2; i <= n; i++) 
	{
		if (!v[i]) 
		{
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for (rint j = 1; prime[j] * i <= n && j <= cnt; j++) 
		{
			v[i * prime[j]] = 1;
			if (!(i % prime[j])) 
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
}

signed main() 
{
	cin >> n;
	init();
	for (rint i = 1; i <= n; i++) 
	{
		d[i] = 1 + d[i / 10];
		s[i] = s[i - 1] + d[i];
	}
	for (rint i = 1; i <= n; i++) 
	{
		double sum = ((double)log2(d[i]) * d[i] + s[n / i]) * phi[i];
		ans += sum;
	}
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

高洁

前置知识 The Sum of the k-th Powers

求 \((\sum_{i=1}^ni^k) \bmod (10^9+7)\)

答案是一个 \(k+1\) 次多项式,考虑找 \(k+2\) 个值带进去拉格朗日插值

\(n+1\) 组点值\((x_i,y_i)\),有 \(n\) 次多项式 \(f\) 的拉格朗日插值:

\[f(x) = \sum_{i = 0}^n y_i\prod_{j\not =i} \frac{x-x_j}{x_i-x_j} \]

复杂度为 \(O(n^2)\).

在此题中把 \(1\) 到 \(k+2\) 带入,有对于每个 \(i\),分母是\(1\) 乘到 \(i-1\) 再乘上 \(-1\) 乘到 \(i-k-2\),这可以预处理阶乘 \(O(1)\) 处理。分子可以预处理前后缀积来 \(O(1)\) 得到

复杂度为 \(O(n)\)

signed main() 
{
	cin >> n >> k;
	pl[0] = pr[k + 3] = fac[0] = 1;
	
	for (rint i = 1; i <= k + 2; i++) pl[i] = pl[i - 1] * (n - i) % mod;
	for (rint i = k + 2; i >= 1; i--) pr[i] = pr[i + 1] * (n - i) % mod;
	for (rint i = 1; i <= k + 2; i++) fac[i] = fac[i - 1] * i % mod;
	for (rint i = 1; i <= k + 2; i++) 
	{
		y = (y + qpow(i, k)) % mod;
		int a = pl[i - 1] * pr[i + 1] % mod;
		int b = fac[i - 1] * ((k - i) & 1 ? -1 : 1) * fac[k + 2 - i] % mod;
		ans = (ans + y * a % mod * qpow(b, mod - 2) % mod) % mod;
	}
	cout << (ans + mod) % mod << endl;
	return 0;
}

在看我们的原题

\(v(i)\) 只和 \(\gcd(i,d)\) 有关。枚举 \(d\) 的因数,考虑它的倍数对答案的贡献。

结果为 \(\begin{aligned}\sum_{i\mid d}\sum_{j=1}^{n/i} (ij)^{v(i)}[\gcd(j,d/i)==1]\end{aligned}\)。

整理得:

\(\begin{aligned}\sum_{i\mid d}i^{v(i)+1}\sum_{j=1}^{n/i}j^{v(i)+1}[\gcd(j,d/i)==1] &amp;=\sum_{i \mid d}i^{v(i)+1}\sum_{j=1}^{n/i}j^{v(i)+1}\sum_{p \mid i,j}\mu(p) \\&amp;=\sum_{i \mid d}i^{v(i)+1}\sum_{p \mid \frac{d}{i}}\mu(p)\sum_{j=1}^{n/i/p} j^{v(i)+1}\end{aligned}\)

\(v(i)\) 为 \(d\) 的所有质因子在 \(d\) 中出现次数与在 \(i\) 中出现次数的商的最大值,可以在枚举 \(i\) 时计算。\(\sum_{i=1}^n i^k\) 前置只是里有的。所以这个题就解决了。

int getpow(int n, int k) 
{
	n = n % mod;
	pl[0] = pr[k + 3] = fac[0] = 1;
	int ans = 0, y = 0;
	for (rint i = 1; i <= k + 2; i++) pl[i] = pl[i - 1] * (n - i) % mod;
	for (rint i = k + 2; i >= 1; i--) pr[i] = pr[i + 1] * (n - i) % mod;
	for (rint i = 1; i <= k + 2; i++) fac[i] = fac[i - 1] * i % mod;
	for (rint i = 1; i <= k + 2; i++) 
	{
		y = (y + qpow(i, k)) % mod;
		int a = pl[i - 1] * pr[i + 1] % mod;
		int b = fac[i - 1] * ((k - i) & 1 ? -1 : 1) * fac[k + 2 - i] % mod;
		ans = (ans + y * a % mod * qpow(b, mod - 2) % mod) % mod;
	}
	return (ans + mod) % mod;
}

void solve(int x) 
{
	memset(c, 0, sizeof c);
	for (rint i = 2; i * i <= x; i++)
	{
		if (!(x % i)) 
		{
			p[++cnt] = i;
			while (!(x % i)) 
			{
				x /= i;
				c[cnt]++;
			}
		}		
	}
	if (x > 1) p[++cnt] = x, c[cnt] = 1;
}

void dfs_init(int x, int step) 
{
	if (x > cnt) 
	{
		int p2 = 1, flag = 1;
		for (rint i = 1; i <= cnt; i++) 
		{
			if (t[i] > 1) flag = 0;
			else if (t[i] == 1) flag = -flag;
			for (rint j = 1; j <= t[i]; j++) p2 *= p[i];
		}
		if (!flag) return ;
		res2 = (res2 + flag * qpow(p2, step) * getpow(n / p1 / p2, step) % mod) % mod;
		return ;
	}
	for (rint i = 0; i <= c[x] - k[x]; i++)
	{
		t[x] = i;
		dfs_init(x + 1, step);		
	}
}

void solve(int d, int p1, int step) 
{
	if (d == 1) step = 1;
	step++;
	int res = qpow(p1, step);
	res2 = 0;
	dfs_init(1, step);
	ans = (ans + res * res2 % mod) % mod;
}

void dfs(int x) 
{
	if (x > cnt) 
	{
		p1 = 1;
		int maxx = 0;
		bool flag = 1;
		for (rint i = 1; i <= cnt; i++)
		{
			flag &= (k[i] > 0);
			for (rint j = 1; j <= k[i]; j++) p1 *= p[i];
			if (k[i]) maxx = max(maxx, (c[i] + k[i] - 1) / k[i]);
		}
		solve(d, p1, flag ? maxx : 0);
		return ;
	}
	for (rint i = 0; i <= c[x]; i++)
	{
		k[x] = i;
		dfs(x + 1);		
	}
}

signed main() 
{
	fac[0] = 1;
	for (rint i = 1; i <= 30; i++) fac[i] = fac[i - 1] * i % mod;
	int T;
	cin >> T;
	while (T--) 
	{
		cin >> n >> d;
		cnt = ans = 0;
		solve(d);
		dfs(1);
		cout << (ans % mod + mod) % mod << endl;
	}
	return 0;
}

理性

把式子展开有一个关于 \(a\) 的二次函数:

\[\sum_{i = 1}^n d_i^2 a^2 + 2(b - v_i)d_i \times a + (b - v_i)^2\\ \]

这个函数的二次项始终为正数,当 \(a\) 取对称轴时函数取到最小值:

\[a = \frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\\ \left(\sum_{i = 1}^n d_i^2\right)\left(\frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\right)^2 + 2\left(\sum_{i = 1}^n (b - v_i)d_i\right)\left(\frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\right) + \left(\sum_{i = 1}^n (b - v_i)^2\right)\\ \frac{(\sum_{i = 1}^n v_id_i)^2 - 2(\sum_{i = 1}^n v_id_i)(b\sum_{i = 1}^n d_i) + b^2(\sum_{i = 1}^n d_i)^2}{\sum_{i = 1}^n d_i^2} + 2\left(b \sum_{i = 1}^n d_i - \sum_{i = 1}^n v_id_i\right)\left(\frac{\sum_{i = 1}^n v_id_i - b \sum_{i = 1}^n d_i}{\sum_{i = 1}^n d_i^2}\right) + \left(\sum_{i = 1}^n b^2 - 2bv_i + v_i^2\right)\\ svd = \sum_{i = 1}^n v_id_i, sd = \sum_{i = 1}^n d_i, sd2 = \sum_{i = 1}^n d_i^2, sv = \sum_{i = 1}^n v_i, sv2 = \sum_{i = 1}^n v_i^2\\ nb^2 - 2sv \times b + sv2 - \frac{b^2 \times sd^2 - 2svd \times sd \times b + svd^2}{sd2}\\ \left(n - \frac{sd^2}{sd2}\right)b^2 + 2\left(\frac{svd \times sd}{sd2} - sv\right)b + sv2 - \frac{svd^2}{sd2}\\ \]

代入后得到了一个只与 \(b\) 有关的二次函数, \(n - \frac{sd^2}{sd2}\) 一定 \(\ge 0\)

所以,再让 \(b\) 取对称轴时函数取到最小值

\[b = \frac{sv - \frac{svd \times sd}{sd2}}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \frac{(sv - \frac{svd \times sd}{sd2})^2}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \frac{sv^2 - 2sv\frac{svd \times sd}{sd2} + \left(\frac{svd \times sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \left(\frac{sv^2}{n - \frac{sd^2}{sd2}} - 2\frac{\frac{sd}{sd2}}{n - \frac{sd^2}{sd2}}sv \times svd + \frac{\left(\frac{sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}svd^2\right)\\ sv2 - \frac{svd^2}{sd2} - \frac{\left(\frac{sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}svd^2 - \frac{sv^2}{n - \frac{sd^2}{sd2}} + 2\frac{\frac{sd}{sd2}}{n - \frac{sd^2}{sd2}}sv \times svd\\ \]

得到了对于一个固定的 \(v\), \(sd, sd2\) 都已知,所以只要求出 \(sv2, svd^2, sv^2, sv \times svd\) 的期望即可。

考虑 \(sv2\)。显然有:

\[sv2 = \sum_{i = 1}^n \frac{S_2(l_i, r_i)}{r_i - l_i + 1} \]

直接计算即可。

设状态 \(f_{i, 0 / 1 / 2 / 3 / 4}\) 分别表示 \(sv, svd, sv^2, sv \times svd, svd^2\) 只考虑前 \(i\) 项的期望,转移方程:

\[f_{i, 0} = f_{i - 1, 0} + \frac{l_i + r_i}2\\ f_{i, 1} = f_{i - 1, 1} + d_i\frac{l_i + r_i}2\\ f_{i, 2} = f_{i - 1, 2} + (l_i + r_i)f_{i - 1, 0} + \frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\ f_{i, 3} = f_{i - 1, 3} + \frac{l_i + r_i}2f_{i - 1, 1} + d_i\frac{l_i + r_i}2f_{i - 1, 0} + d_i\frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\ f_{i, 4} = f_{i - 1, 4} + d_i(l_i + r_i)f_{i - 1, 1} + d_i^2\frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\ \]

void add(int &x, int y) {x = (x + y) % mod;}
void mul(int &x, int y) {x = x * y % mod;}

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int inv(int x){return qpow(x, mod - 2);}
int calc(int x){return x * (x + 1) % mod * (x << 1 | 1) % mod * iv6 % mod;}
int calc(int l, int r) {return (calc(r) - calc(l - 1) + mod) % mod;}

signed main() 
{
	cin >> n;
	
	for (rint i = 1; i <= n; i++)
	{
		cin >> d[i] >> l[i] >> r[i];
		add(sd,  d[i]);
		add(sd2, d[i] * d[i] % mod);
	}
		      
	for (rint i = 1; i <= n; i++) 
	{
		int iv = inv(r[i] - l[i] + 1);
		add(ans, calc(l[i], r[i]) * iv % mod);
		add(f[i][0] = f[i - 1][0], (l[i] + r[i]) * iv2 % mod);
		add(f[i][1] = f[i - 1][1], (l[i] + r[i]) * iv2 % mod * d[i] % mod);
		add(f[i][2] = f[i - 1][2], calc(l[i], r[i]) * iv % mod);
		add(f[i][2], (l[i] + r[i]) * f[i - 1][0] % mod);
		add(f[i][3] = f[i - 1][3], calc(l[i], r[i]) * iv % mod * d[i] % mod);
		add(f[i][3], (l[i] + r[i]) * f[i - 1][1] % mod * iv2 % mod);
		add(f[i][3], (l[i] + r[i]) * f[i - 1][0] % mod * iv2 % mod * d[i] % mod);
		add(f[i][4] = f[i - 1][4], calc(l[i], r[i]) * iv % mod * d[i] % mod * d[i] % mod);
		add(f[i][4], (l[i] + r[i]) * f[i - 1][1] % mod * d[i] % mod);
	}
	
	int q = inv((n - sd * sd % mod * inv(sd2) % mod + mod) % mod);
	
	add(ans, mod - f[n][4] * inv(sd2) % mod);
	add(ans, mod - f[n][4] * qpow(sd * inv(sd2) % mod, 2) % mod * q % mod);
	add(ans, mod - f[n][2] * q % mod);
	add(ans, 2 * f[n][3] * sd % mod * inv(sd2) % mod * q % mod);
	
	cout << ans << endl;
	
	return 0;
}

标签:frac,sd2,int,sum,T1,七道,照亮,svd,sd
From: https://www.cnblogs.com/spaceswalker/p/18158730

相关文章

  • web server apache tomcat11-21-monitor and management 监控与管理
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-16-mbean
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-14-CGI
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • 痞子衡嵌入式:在i.MXRT1xxx系列上用NAND型启动设备时可用两级设计缩短启动时间
    大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家分享的是在i.MXRT1xxx系列上用NAND型启动设备时可用两级设计缩短启动时间。去年痞子衡写过一篇骚操作文章《借助i.MXRT10xx系列INIT_VTOR功能可以缩短程序热重启时间》,这对于NAND型启动设备上程序热重启时间的......
  • web server apache tomcat11-12-SSL/TLS Configuration
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • JVM-part1-类加载子系统组成,及流程
    类加载子系统的作用:将所需要的Class文件进行加载,加载流程存在一下几个阶段:第一个阶段为加载阶段(Loading阶段):这个阶段是将引导类加载器和非引导类加载器需要加载的Class文件进行加载。具体来说:引导类加载器(BootStrapClassLoader):这个加载器的作用是将java_home/jre/lib下的Cl......
  • web server apache tomcat11-10-Class Loader
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • FineReport11 报表技巧02- 实现类Excel表头筛选功能
    背景:在报表开发中,有的需求方用习惯Excel的表头筛选时,就不太习惯帆软的特意点击报表控件进行筛选,希望报表筛选方式可以类似Excel那种直接在表头进行筛选的功能最终效果如下:实现步骤:1.1、数据集准备产品信息表:SELECT客户,产品,数量,cast(下单时间asdate)as下单时间,下单......
  • web server apache tomcat11-08-JNDI Resources
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • FineReport11 报表技巧01- 单元格HTML显示tag颜色标签
    背景FineReport报表制作中,经常需要将某些单元格内容以彩色标签显示,其中根据不同对象内容进行不同展示,效果如下图所示:实现效果为:1、“年龄”列内容根据年龄段不同显示为不同颜色且带边框效果;2、“性别”列性别为“男”显示为蓝色,性别为“女”显示为红色,性别为“未知”显示为灰......