文本串为A(长度为n)A(长度为n)A(长度为n)，模式串为B(长度为m)B(长度为m)B(长度为m) 不考虑通配符的时候，可以用完全匹配函数可以是P(x)=∑i=0m−1[B(i)−A(x−m+1+i)<mtext> </mtext>]2{P(x)=\sum_{i=0}^{m-1}{[B(i)-A(x-m+1+i)\ ]^2}}P(x)=∑i=0m−1​[B(i)−A(x−m+1+i) ]2 将通配符赋值为000，那么有完全匹配函数P(x)=∑i=0m−1[B(i)−A(x−m+1+i)<mtext> </mtext&g...

A.size()==n>=B.size()==mA.size()==n>=B.size()==mA.size()==n>=B.size()==m 定义完全匹配函数：P(x)=∑i=0m−1[B(i)−A(x−m+1+i) ]2{P(x)=\sum_{i=0}^{m-1}{[B(i)-A(x-m+1+i)\ ]^2}}P(x)=∑i=0m−1​[B(i)−A(x−m+1+i) ]2 则有P(x)=∑i=0m−1[B(i)2+A(x−m+1+i)2−2∗B(i)∗A(x−m+1+i)]{P(x)=\sum_{i=0}^{m-1}{[B(i)^2+A(x-m+1...

NTT模板： #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=3e5+10,mod=998244353; inline int qpow(int x,int y) { int res(1); while(y) { if(y&1) res=1LL*res*x%mod; x=1LL*x*x%mod; y>>=1; } return res; } int r[maxn]; inline void ntt(int *x,int lim,int opt) {...

实验任务及结果 201926701052-杨文冠-试验一  使用jps命令查看三台虚拟机下Hadoop相关进程并截图     在浏览器中查看集群运行主界面，并截图   配置过程

201926701052-杨文冠 1.create：创建表 create 'tbl_user', 'info', 'detail'  2.alter：修改表结构 2.1 添加一个列族 alter 'tbl_user', 'address'  2.2 删除一个列族 alter 'tbl_user', {NAME=> 'address', METHOD=> 'delete'}  2.3 修改列族的属性 # 修改region的最大大小为128MB lter 't1', MAX_FILESIZE => '134217728' # 修改f1列族的版本为6 alter 't1', NAM...

，求出最小的满足，不存在输出。 有原式可知未知。 将用原根表示，从而将乘法变成加法，的原根是，则，可得  观察可知，的意义同上。 这个式子显然能带入快速幂，快速幂主要是求解出的系数，所以将式子带入后就能求出。 所以现在问题就变成了求解已知，直接上模板。 code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353,_mod=mod-1,maxn=(1<<16)-1; int gcd(int a,int b) { if(!b) return...

求出的所有解。 找到一个特解 因为是质数，所以可以求出的质数。因此对于模意义下的任意数有且仅有一个数满足。 假设，则，稍加变换，有：  然后套用就一定能求出，然后得到原方程的一个特解 找到所有解   则， 对上面的式子，显然有，设，则有  code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1<<16)-1; int gcd(int a,int b) { if(!b) return a; while((a%=b) && (b%=...

求解：  博客 code: const int maxn=(1<<16)-1; struct HASH{ int v[maxn+1],tot,ed=0; struct node{ int t,p,next; }a[maxn<<1]; void ins(int x,int y) { int k=x&maxn; if(v[k]!=ed) { v[k]=ed; a[k].t=x,a[k].p=y,a[k].next=0; } else { for(;;k=a[k].next) { if(a[k].t==x) return a[k].p=y,void(); if(!a[...

欧几里得： int gcd(int a,int b) { if(!b) return a; while((a%=b) && (b%=a)); return a+b; } 扩展欧几里得： int exgcd(int a, int b, int &x, int &y) { int x1 = 1, x2 = 0, x3 = 0, x4 = 1; while (b != 0) { int c = a / b; tie(x1, x2, x3, x4, a, b) = make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b...

对于第一个任务，上快速幂。 对于第二个任务，因为是质数，就不需要扩展欧几里得求逆元了，直接快速幂求逆元。 对于第三给任务，上。 原式：   ，则， 枚举，然后用存起来：。接着从小到大枚举，如果，那么最小的。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e4+7; ll qpow(ll a,ll b,int mod) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1;...

求解：，不一定互质。 如果，则存在逆元，直接使用求解。 具体的，假设，如果，方程无解。否则，方程同时除以：  直到 记，于是方程变成：  套时，没必要计算出的逆元然后挪到等式右边，只需要在枚举时查找是否存在即可。 注意，不排除小于等于的情况，也就是可能说在还没有达到时就有解了，这个需要特判。 这题卡常，需要用比较快的哈希板子。 code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1<<16)-1; struct HASH{ int v[maxn+...

求解：  因子和函数的一个特殊的性质，      带回原式,有：      预处理筛出函数，然后分块处理询问。 code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e4+7; int mu[maxn]; ll d[maxn],t[maxn]; bool vis[maxn]; vector<int>prime; inline void init() { d[1]=mu[1]=1; for(int i=2,x,y;i<maxn;++i) { ...

为了方便计算，这里用变量名表示题目中的 求解：  则原式：    自然数幂和是一个次多项式，可以用伯努利数算出系数，不妨记为 由伯努利公式得： 则原式：   令，易知是积性函数，令，则有   则 Code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=107,mod=1e9+7; ll qpow(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1;...

求值：  易得原式如下：  枚举最大公因数：  非常经典的式子的化法：  式子的后半段出现了互质数对之积之和，考率先单独拿出来,记  有：    观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记  可以求解。 至此：  我们可以数论分块求解这部分。 回到定义的地方，则原式为：  这又是一个可以数论分块求解的式子。 Code: #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e7+7,mod=20101009; int mu[maxn]; ll f[...