4.5省选练习
\(T1\)
\(emm,\)爆搜\(?\)好久没见过搜索题了...
一样的就跳,不一样的就改\(TAT\)
#include
#define MAXM 1000010
#define MAXN 210
using namespace std;
char *a,*b;
int len[MAXN];
string s[MAXN];
int ans[10],ans1,n;
void work(int i,int j,int leni,int lenj,int cnt)
{
if(cnt+abs(leni-i+j-lenj)>=ans1)return;
while(i>s[i];
len[i]=strlen(s[i].c_str());
}
for(int i=0;i \(T2\)
感觉和特征多项式有点关系\(?\)
确实有点关系,这种题都能推通项公式吧,利用特征根求
\(A_n=p\times 3^n+q\times(-1)^n\)
推导一下
\(f[x]=a\times f[x-1]+b\times f[x-2]\)
\(f[x]-t\times f[x-1]=k\times(f[x-1]-t\times f[x-2])\)
\(f[x]=(k+t)\times f[x-1]-k\times t\times f[x-2]\)
最后
\(a_n-\lambda a_{n-1}=\mu(a_{n-1}-\lambda a_{n-2})\)
\(\left\{\begin{matrix} \lambda = 3\\ \mu = -1\end{matrix}\right.\text{}\left\{\begin{matrix} \lambda = -1\\ \mu = 3 \end{matrix}\right.\)
最后带回得到
\(4f(n-1)=(3^{n-1}+(-1)^{n-2})(f(2)-f(1))\)
最后得到
\(A_n=p\times 3^n+q\times(-1)^n\)
我们只需要对两个分别计算贡献
我们对于每一个位置扔一个\((1+3^{a_i}x)\)最后求出来\(x^k\)是恰好全\(k\)个的\(3^z\)和
直接分治\(FFT\)即可
#include
#define MAXN 524298
using namespace std;
const int p=99991;
const long double pi=acos(-1);
int n,K,a[MAXN];
struct node
{
long double x,y;
node(long double xx=0,long double yy=0){x=xx,y=yy;}
node operator - (const node &B){return node(x-B.x,y-B.y);}
node operator + (const node &B){return node(x+B.x,y+B.y);}
node operator * (const node &B){return node(x*B.x-y*B.y,x*B.y+y*B.x);}
node operator * (const long double &B) {return node(x*B,y*B);}
}A[MAXN],B[MAXN],C[MAXN],w[MAXN];
int rev[MAXN];
void FFT(node *A,int n,int op)
{
for(int i=1;ii) swap(A[i],A[rev[i]]);
}
node x,y;
for(int k=2;k<=n;k<<=1)
{
for(int i=0;i>1);j++)
{
x=A[i+j],y=w[n/k*j]*A[i+j+(k>>1)];
A[i+j]=x+y;
A[i+j+(k>>1)]=x-y;
}
}
}
if(op==-1)
{
long double tmp=1.0/n;
for(int i=0;i=p) ttmp[i+j]-=p;
}
}
for(int i=0;i>1]>>1)|((i&1)<>=1;
}
return ans;
}
int an[20][MAXN];
inline void work(int l,int r,int dep)
{
if(l==r)
{
an[dep][0]=1;
an[dep][1]=my_pow(3,a[l]);
return ;
}
int mid=(l+r)>>1;
work(l,mid,dep+1);
for(int i=0;i<=(mid-l+1);i++) an[dep][i]=an[dep+1][i];
work(mid+1,r,dep+1);
wor(an[dep],an[dep+1],an[dep],mid-l+2,r-mid+1);
}
int jc[MAXN],ni[MAXN];
int get_c(int a,int b)
{
if(b>a)return 0;
return 1ll*jc[a]*ni[b]%p*ni[a-b]%p;
}
int js[5];
int work2()
{
jc[0]=ni[0]=1;
for(int i=1;i \(T3\)
原题