https://oi-wiki.org/math/linear-recurrence/https://zerol.me/2018/02/06/linearly-recurrent-sequence/https://blog.csdn.net/myjs999/article/details/86433706https://www.cnblogs.com/autoint/p/berlekamp-massey_algorithm.htmlhttps://codeforces.com/blog/entry/61306

https://vjudge.net/contest/409076#problem/G #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; ll qp(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; }return res; } ll cnt1(ll a)//对i^2求和. { return a*(a+1)%mod*(2*a+1)*qp(6...

1.算法分析(DP) 考虑dp,我们令f[i][j]表示,到了第i个差值为两者j的方案数.很容易想到n^4的暴力dp.这里贴下代码. #include<bits/stdc++.h> using namespace std; const int N=210,M=N*N*2; const int mod=1e9 + 7; int s[M],n,f[N][M],a[N],base=200*200; int main() { cin>>n;int sum=0; for(int i = 1;i <= n;i++) scanf("%d",&a[i]...

mark:1.http://www.51nod.com/Challenge/Problem.html#problemId=3173 2.http://www.51nod.com/Challenge/Problem.html#problemId=3152 3.https://codeforc.es/contest/1446/problem/C 4.https://codeforc.es/gym/101864/attachments G题

1.题目大意: 时隔六日,爷终于会了,不就是点分树吗?(有手就行..咦,不对,我手呢?)来看看这个题目,这个题目是说你有一颗树啊.然后两个操作.第一个操作是:查询u距离不超过k的点权和.第二个操作是:修改u的点权.  2.解题思路: 很快啊,大佬很快就会做了,我大意了,看了三天.原来大佬是有备(动态开点)而来.正题:首先在学点分树前先学动态开点,lca,虚树,点分治,容斥.学完这些学这个算法就很简单了.因为这个算法就是这些算法的集合.对于这个题目的步骤如下:1.先dfs一下,处理原树的深度.和预处理f[i][j]倍增数组,表示i这个点,2^j上是哪个点,这里我们拿1当作根节点.然后搜一下就完事...

幸好有大佬帮我,不然就死翘翘了hhh #include <bits/stdc++.h> using namespace std; const int N=3e4+50; int dis[N],vis[N],n,m,k; struct node{ int to,val; bool operator <(const node &res)const{ return to<res.to; }; }; struct vv{ int to,val; }; struct Q{ int to,val; bool operator <(const Q &res)co...

第一道点分治的题目,感觉代码难写hhh,大概思路就是染色法+双指针模拟+分治吧~//.. #include <bits/stdc++.h> using namespace std; const int N=4e4+40; struct node{ int to,val; }; vector<node>G[N]; int root,color[N],f[N],dp[N],sum,vis[N],ans,siz[N],dis[N],heap[N],id,k,n; bool cmp(int a,int b) { return dis[a]<dis[b]; } void f...

代码很多注释/// //给你一个数x,然后要你找到两个数a,b使得b=x+a,且a,b位数不一样.要你求这样的a,b个数. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=55; ll x,n,a[N]; ll span[N];//这一位假如进位可以到哪一位. ll f[N];//到i的时候进位不进位可以有多少种方案数. ll cnt[N];//记录每一位的大小. ll possible[N];//可以进位的方案数 int main() { //a+x=b,且a,b位数不能...

误入点分治题单的一个期望dp.对于这个题来说,我们不妨设置f[i]为i-1分到i分所需要的次数(我们把50分看做1分.),然后他的转移也不难.对于f[i-1]来说,它可以一步就就到f[i],也可能-2再到f[i],所以概率方程就是:  f[i]=p+(1-p)*(1+f[i-2]+f[i-1]+f[i]). ->f[i]=1+((1-p)/p)*(1+f[i-2]+f[i-1]).嗦嘎,如此这个题目就完成了,ans=tot(f[1...20])-f[20].因为答案必定是950,1000的形式.然后关于初值,也是看这个方程得到的,因为f[0]=0和f[-1]不存在可以看成0,所以f[1]...

https://vjudge.net/problem/HDU-4870 pass(hint:This is a Expected DP) https://www.luogu.com.cn/problem/P4178 pass(这是一个模板题) https://vjudge.net/problem/HDU-4871 pass(感谢大佬帮我debug.) https://vjudge.net/problem/HDU-4918 pass(虽然是点分树的模板题,但是我觉得挺难的) https://vjudge.net/problem/HDU-5469 https://vjudge.net/proble...

https://vjudge.net/contest/406685 附带一份洛谷日报:https://baijiahao.baidu.com/s?id=1613444794783555531&wfr=spider&for=pc

题目是给你n个数,两两之间可以合并,问你最少合并多少次,可以使得序列是递增序列?数据范围是O(N)解决.我们很容易联想到f[i]表示前i个满足最少需要合并多少次?然后也容易想到一种错误的贪心想法,就是从前往后能不用就不用,选完就好.之所以这种不一定对是因为这种不能最小化代价,代码有hack数据.考虑f[i],我们可以选的话.(先有一个证明,f[i+1]<=f[i]+1.因为我们可以把i+1个并给第i个.)在有这个证明的基础上,考虑转移的条件(if(sum[i]>=sum[j]+last[j]))在我们选择的时候,假如l<r,且sum[r]+last[r]<=sum[l]...

Mark有时间更~ https://ac.nowcoder.com/acm/contest/8891

启发式合并顾名思义就是得到启发后进行合并.把原本合并时的(n>m) O(nlogm)->O(mlogn).本题题意那么长,说白了就是给你n段,然后询问在所有段最多重叠k次可以的最大权值是多少.直接建树分治合并即可~代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e6+56; typedef long long ll; struct FZ{ int l,r; ll w; }tr[N]; bool cmp(FZ a,FZ b) { if(a.l==b.l) return a.r>b.r;...