首先感性感觉这个东西是比较有循环节的,但这是后话。
最后几步一定是 差分相同->每个数相同->全为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