首页 > 其他分享 >云斗杯 T2 派蒙是最好的伙伴! 题解

云斗杯 T2 派蒙是最好的伙伴! 题解

时间:2023-07-16 09:11:43浏览次数:41  
标签:云斗杯 tmpa 蒙是 ++ 题解 矩阵 ta tb mod

云斗杯 T2 题解

赛时脑抽了只打了 60pts 暴力 xwx。

题目描述

给定两个长度为 \(n\) 的 \(01\) 序列 \({a_n}\) 和 \({b_n}\),与另一个矩阵 \({c_{n,n}}\)。矩阵 \({c_{n, n}}\) 的生成规则如下:

\[c_{i, j} = a_i \times b_j \]

现给定一个数 \(k\),求在矩阵 \(c_{n, n}\) 内,有多少个连续子矩阵满足其中有 \(k\) 个 \(1\)?

样例 #1

样例输入 #1

4 4
0 1 1 1
1 0 1 0

样例输出 #1

6

样例解释
如图,取蓝色字部分、米色背景部分、两个粗线框内部,以及小粗线框加上紫色或绿色的 \(0\) 构成的矩阵均符合题意。

数据范围

$1 \leq n \leq 3 \times 10^5, 1 \leq k \leq 10^{12} $

思路

首先看到 \(n\) 的范围意识到这个矩阵没法直接求出来,只能转化题意。
然后我们来考虑一个包含 \(k\) 个 \(1\) 的矩阵应该怎样生成,发现,一个子矩阵包含 \(k\) 个 \(1\),当且仅当这个子矩阵对应的两个序列中的区间和乘积为 \(k\)。这个结论很好证明,因为每一个 \(a\) 中的 \(1\) 都可以与 \(b\) 中对应列上的 \(1\) 生成一个 \(1\)。
那么,现在问题就转化为了求两个序列中,区间和为 \(k\) 的某个因数的区间的个数。如果暴力去 \(dp\),会发现要 \(n^2\) 枚举。但是,这样做会枚举到很多没用的数,且会浪费很多信息。我们又知道,\(10^{12}\) 以内的数最多有 \(6720\) 个不同的因数;而且,\(n\) 只有 \(3 \times 10^5\),这也就意味着,有很多 \(k\) 的因数是超出 \(n\) 的范围的。所以,我们直接枚举 \(k\) 的所有因数,然后用前缀和+双指针直接处理即可。
代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5+100;
const int mod = 998244353;

inline ll read(){
	ll x = 0; char ch = getchar();
	while(ch<'0' || ch>'9') ch = getchar();
	while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
	return x; 
} 
int a[N], b[N];
ll sa[N], sb[N];
int n; ll K;
ll fa[N], fb[N];
ll yin[10000], toty;
int main(){
	n = read(), K = read();
	for(ll i = 1; i*i<=K; ++i){
		if(K%i) continue;
		yin[++toty] = i;
		if(K/i!=i) yin[++toty] = K/i;
	}
	for(int i = 1; i<=n; ++i){
		a[i] = read();
		sa[i] = sa[i-1]+a[i];
	}
	for(int i = 1; i<=n; ++i){
		b[i] = read();
		sb[i] = sb[i-1]+b[i];
	}
//	for(int i = 1; i<=n; ++i){
//		for(int j = 1; j<=i; ++j){
//			++fa[sa[i]-sa[j-1]];
//		}
//	}
//	for(int i = 1; i<=n; ++i){
//		for(int j = 1; j<=i; ++j){
//			++fb[sb[i]-sb[j-1]];
//		}
//	}//暴力部分 xwx
	int ans = 0;
	for(ll i = 1; i<=toty; ++i){
		ll yina = yin[i], yinb = K/yin[i];
		if(yina > sa[n] || yinb > sb[n]) continue;
		ll tmpa = 0, tmpb = 0;
		for(int l = 1, r = 1, ta = 0, tb = 0; r<=n; ++r){
			if(sa[r] < yina) continue;
			while(sa[r]-sa[l-1] > yina) ++l, ++ta;
			if(sa[r]!=sa[r-1]){
				tmpa = (tmpa+1ll*ta*tb%mod)%mod;
				ta = 0, tb = 0;
			}
			++tb;
			if(r == n){
				while(sa[r]-sa[l-1] == yina) ++l, ++ta;
				tmpa = (tmpa+ta*tb%mod)%mod;
			}
		}
		for(int l = 1, r = 1, ta = 0, tb = 0; r<=n; ++r){
			if(sb[r] < yinb) continue;
			while(sb[r]-sb[l-1] > yinb) ++l, ++ta;
			if(sb[r]!=sb[r-1]){
				tmpb = (tmpb+ta*tb%mod)%mod;
				ta = 0, tb = 0;
			}
			++tb;
			if(r == n){
				while(sb[r]-sb[l-1] == yinb) ++l, ++ta;
				tmpb = (tmpb+1ll*ta*tb%mod)%mod;
			}
		}
		ans = (ans+1ll*tmpa*tmpb)%mod;
	}
//	for(int i = 1; i<=n; ++i){
//		if(K%i) continue;
//		if(i>sa[n]) continue;
//		ll tmp = K/i;
//		if(tmp>sb[n]) continue;
//		ans = (1ll*ans+1ll*fa[i]*fb[tmp]%mod)%mod;
//	}
	printf("%d\n", ans);
	return 0;
} 

标签:云斗杯,tmpa,蒙是,++,题解,矩阵,ta,tb,mod
From: https://www.cnblogs.com/frostwood/p/17557417.html

相关文章

  • [YDRG#001] 提瓦特环游记 · 云斗杯 · 七月 Golden 组模拟赛 整理分析--zhengjun
    link总体评价:因为K了,所以好评,练一下思维蛮好的,质量不错比赛2.5hK的。#A.诗人小G初进OI界标准送分,输出\(\frac{s_2-a_2}{a_1}\)。#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e6+10;intn,a[N];voidread(ll&x){ char......
  • freee Programming Contest 2023(AtCoder Beginner Contest 310)题解
    点我看题A-OrderSomethingElse直接比较\(P\)和\(Q+min(D_i)\),输出较小值即可。点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#defi......
  • AJAX请求,响应头有set-cookie但浏览器不能写入cookie问题解决!
    开幕雷击:AJAX就不是干这个ajax只有向服务器发送请求时带上cookie的功能可选。不存在ajax向服务器get的时候带回来cookie的功能。解决把AJAX代码改成原始的js代码来完成需求:正确的jsdocument.addEventListener('DOMContentLoaded',function(){document.querySelector('......
  • CF339 题解
    CF339题解这套题虽然是div2,但是具有一定的价值,这套题作为典型的div2题目,全套5道题都几乎用暴力方法解决,但是为什么这样是对的?令人深思。A红题,把个位数提出来再排序就好了。#include<bits/stdc++.h>usingnamespacestd;constintN=105;chars[N];intn,num[N],tot=0......
  • P1891 疯狂 LCM 题解
    一、题目描述:$T$ 组数据,每组数据给定$n$,求$\sum_{i=1}^{n}lcm(i,n)$数据范围:$1\leT\le3\times10^5,1\len\le1\times10^6$。 二、解题思路:个人觉得思维难度不大,只是要记住一个结论:$\sum_{d\midn}d=\frac{\varphi(n)\timesn}{2}$这个公式对......
  • VMware17无法连接USB设备的问题解决方案
    前言【前言都是废话,可以直接看解决方案】事情是这样的,最近在做IMX6ULL的开发,刚开始就遇到了这个拦路虎问题,我使用的闪迪的TF卡32GB的,搭配绿联的读卡器使用。在windows以及物理机装的archlinux都能正常识别并进行挂载,离谱的就是在虚拟机上识别不了。虚拟机版本:VMwareWorkstati......
  • CF1220F Gardener Alex 题解--zhengjun
    发现根节点一定是\(1\),所以考虑两边的子树深度,然后发现只需要考虑一段后缀或前缀的深度即可。所以循环位移后,可以从中间往两边构建笛卡尔树,实时维护深度即可。代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=2e5+10;intn,a[N],ans[N];......
  • CF732E Sockets 题解
    功率是\(x\)的插座插入一个适配器后功率是\(y\),功率是\(y\)的插座插入一个适配器后功率是\(z\),那么相当于功率是\(x\)的插座插入两个适配器。一个电脑可以用功率小的插座插入较少的适配器表达,也可以用功率大的插座插入较多的适配器表达。这里功率大的插座必然能表达出功......
  • 题解 [NOIP2015 提高组] 运输计划
    题目链接闲话:虽说是紫题,但慢慢想还是完全没有问题的。由于\(m\)个运输计划同时开始,所以耗费时间就是最慢的飞船耗费的时间(即最长时间)。考虑到题目让求最短时间,也就是最长的最短,可以二分。考虑二分最长时间(记作\(k\)),那么将所有路径分成两类,一类是原来耗费的时间就小于等于\(......
  • QOJ 6504. CCPC Final 2022 D Flower's Land 2题解
    QOJ6504.CCPCFinal2022DFlower'sLand2题解题意简述给你一个只含\(0,1,2\)的序列,相邻两个相同的数字可以直接消掉。询问包含两种区间所有数\(+1\)并对\(3\)取模。求一段区间能否用上述消除方式消完。样例输入8901211012245236168168236......