首页 > 其他分享 >THUPC2019 令人难以忘记的题目名称 题解

THUPC2019 令人难以忘记的题目名称 题解

时间:2023-02-24 22:14:30浏览次数:97  
标签:题目 int 题解 差分 THUPC2019 序列 次后

首先感性感觉这个东西是比较有循环节的,但这是后话。

最后几步一定是 差分相同->每个数相同->全为0。

不平凡地猜想差分 \(k\) 次全 \(0\) 等价于可以 \(k\) 步胜利。

假设差分 \(k-1\) 次后全为 \(a\),这个序列取反后差分 \(k-1\) 次就全是 \(-a\)。那么选择这个序列就能保证差分 \(k-1\) 次后全是 \(0\)。

另一边的等价性可以归纳证明。

此时列出差分 \(t\) 次的式子:

\(S'_i=\sum_{j=0}^t(-1)^j\binom{t}{j}S_{i+j}\)

带入 \(t=p^k\) 后,发现 \(S'_i=S_i-S_{i+p^k}\)

(注意到 \(p=2\) 时化出来不同,但是最终是一样的)

注意到序列长度是 \(n\),于是可以化成 \(S'_{i}=S_i-S_{i+\gcd(p^t,n)}\)。

如果有解,那么 \(p^t\) 足够大一定有解,假设 \(n\) 对于 \(p\) 的次数为 \(p^c\),那么一定要满足 \(S'_{i}=S_i-S_{i+p^c}\)。

此时有答案不超过 \(p^c\),于是只保留序列的前 \(p^c\) 项继续做,判断 \(p^{c-1}\) 是否合法,合法直接递归,不合法就差分 \(p^{c-1}\) 次递归。

时间复杂度 \(O(np)\)。

#include <bits/stdc++.h>
using namespace std;
const int N=3e5;
int n,p,ans,a[N],b[N];
bool chk(int x){
	for(int i=0;i<n;i++) if(a[i]!=a[(i+x)%n]) return 0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&p);
	for(int i=0,x;i<n;i++) scanf("%d",&x),a[i]=x%p;
	int t=1;
	while(n%(t*p)==0) t*=p;
	if(!chk(t)) return puts("-1"),0;
	while((n=t)>1){
		t/=p;
		for(;!chk(t);ans+=t){
			for(int i=0;i<n;i++) b[i]=(a[i]-a[(i+t)%n]+p)%p;
			copy(b,b+n,a);
		}
	}
	printf("%d\n",ans+(a[0]>0));
	return 0;
}

标签:题目,int,题解,差分,THUPC2019,序列,次后
From: https://www.cnblogs.com/shrshrshr/p/17153114.html

相关文章

  • 计组——大端方式和小端方式以及边界对齐相关题目
    大端方式和小端方式相关题目1.大端方式和小端方式2.边界对齐3.真题嗅探 1.大端方式和小端方式大端方式:现代人正常的阅读顺序,从左向右小端方式:古代人的阅读顺序(联......
  • Universial Cup 题解
    开始瞎做题了全部都写了简要题意,题解默认折叠,可以来做做(?UniversialCup官网The1stUniversalCup比赛名称&题解链接题解包含题目QOJlinkCodeforcesGymLin......
  • 题解 北大集训2018 点分治
    题意给定\(n\)个点的树,求点分治方案数,对\(10^9+7\)取模。两种方案不同当且仅当点分树不同。\(1\leqn\leq5000\)题解考虑怎样合并两个点分治方案。如果我们有......
  • history 题解(并查集)
    考虑使用边带权并查集维护点之间的连通性,边权为这条边建立的时间,查询时如果查询时间小于边权则不能通行(巧妙地处理了时间的性质)。由于时间这种东西性质特殊无法路径压缩,所......
  • 新版 Mac M2 安装老 saas 项目 报 Gem sass is not installed 问题解决
     换了新电脑,需要把老项目git拉下来再跑起来的时候发现生成样式文件的时候会报这个错误,(N年前老项目,用的是node-sass,[email protected]版本比较老旧,但项目还是要......
  • vue——更改路由模式为history后,刷新页面显示Cannot Get/空白/404,本地icon图标不显示
    参考:https://blog.csdn.net/william_jzy/article/details/106526339   https://www.bbsmax.com/A/A7zgKEVkz4/      https://router.vuejs.org/zh/gu......
  • CF1131B 题解
    题目传送门好水的绿题,当放松了。题目分析为了方便表述,定义\(lsta,lstb,nowa,nowb\),分别表示上次双方的得分以及当前的得分。考虑分讨,若\(lsta=lstb\),贡献即\(\min(n......
  • P6666 [清华集训2016] 数据交互 题解
    ##P6666[清华集训2016]数据交互题解###简要题意:n个点的树,m次操作,分别为添加一条路径$(u_i,v_i,w_i)$,和撤消一条路径,每一次操作后求出一条路径使得与这条路径有交的......
  • P8422 题解
    前言题目传送门!更好的阅读体验?第三道大模拟,写篇题解庆祝一下。文中粗体字是我踩坑的地方,欢迎统计我被坑了多少次。思路终局奖分很简单,放在主函数里,所以我们看每次的......
  • 树剖练习题题解总和(动态更新)
    这篇博客的练习题题解1、P3384【模板】轻重链剖分/树链剖分模板题,详见此#include<iostream>#include<cstdio>#include<vector>usingnamespacestd;intn,m,r,p,t[......