T1 基环树直径,一定学
T2 树上斜率优化,类似购票,数据结构/分治算法,一定改
(把点按深度排序倒着跑2e7次斜率优化也能A,orz zyz)
T3 CC原题,码码码,一定补
一定咕
学动态点分治去了
因为各种原因又压进来一篇
T1 神tm 暴力DP+剪枝可过,我觉得反正只会暴力然后就没剪枝,造数据的建议击毙
T2 沙茶博主第一次实际应用生成函数?
根据题目中的递推关系搞出来生成函数
$f[i]=2*f[i-1]+3*f[i-2]$
$x^n=2*x^{n-1}+3*x^{n-2}$
$x^2=2x+3$
解这个方程得到$x=-1$或$x=3$
所以一定有$f_n=k_1(-1)^n+k_23^n$
前两项带进去,解得$k_1=frac{3}{4}f_0-frac{1}{4}f_1,k_2=frac{1}{4}f_0+frac{1}{4}f_1$
现在要我们求集合s的所有大小为k的子集的子集和的对应项之和
考虑上面的那个东西,相当于把所有物品拿出来做背包,最后$k$次项的系数对答案产生贡献,写一个分治FFT来做
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=800005,M=30,mod=99991; 8 const int Pow=15,Bas=(1<<Pow)-1; 9 const double pai=acos(-1); 10 struct cpx 11 { 12 double x,y; 13 void Turn(int a,int b) 14 { 15 x=a,y=b; 16 } 17 }a[N],b[N],c[N],d[N],ort[N]; 18 const cpx b1=(cpx){0.5,0}; 19 const cpx b2=(cpx){0,-0.5}; 20 const cpx b3=(cpx){1,0}; 21 const cpx b4=(cpx){0,1}; 22 cpx operator + (cpx a,cpx b) 23 { 24 return (cpx){a.x+b.x,a.y+b.y}; 25 } 26 cpx operator - (cpx a,cpx b) 27 { 28 return (cpx){a.x-b.x,a.y-b.y}; 29 } 30 cpx operator * (cpx a,cpx b) 31 { 32 double x1=a.x,x2=b.x,y1=a.y,y2=b.y; 33 return (cpx){x1*x2-y1*y2,x1*y2+x2*y1}; 34 } 35 cpx operator ! (cpx a) 36 { 37 a.y=-a.y; return a; 38 } 39 char BF[1<<23],*P1=BF,*P2=BF; 40 char Gc(){return (P1==P2&&(P2=(P1=BF)+fread(BF,1,1<<21,stdin),P1==P2)?EOF:*P1++);} 41 template<class Type> void Fread(Type &x) 42 { 43 x=0; char ch=Gc(); 44 while(!isdigit(ch)) ch=Gc(); 45 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=Gc(); 46 } 47 int Roumod(double x) 48 { 49 return (long long)(x+0.5)%mod; 50 } 51 int Qpow(int x,int k) 52 { 53 if(k==1) return x; 54 int tmp=Qpow(x,k/2); 55 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 56 } 57 #define vint vector<int> 58 #define vit vector<int> ::iterator 59 double Sin[M],Cos[M]; 60 int n,m,f0,f1,k1,k2,anss; 61 int num[N],odf[N],rev[N],xx[N],yy[N],ans[N]; vint fuc; 62 63 void Trans(cpx *cop,int len,int typ) 64 { 65 register int i,j,k; 66 for(i=0;i<len;i++) 67 if(rev[i]>i) swap(cop[i],cop[rev[i]]); 68 for(i=2;i<=len;i<<=1) 69 { 70 int lth=i>>1; 71 for(j=0;j<len;j+=i) 72 { 73 cpx *pts=ort; 74 for(k=j;k<j+lth;pts+=len/lth,k++) 75 { 76 cpx tmp=*pts; if(typ==-1) tmp=!tmp; 77 tmp=tmp*cop[k+lth],cop[k+lth]=cop[k]-tmp,cop[k]=cop[k]+tmp; 78 } 79 } 80 } 81 if(typ==-1) 82 for(int i=0;i<=len;i++) 83 cop[i].x/=len,cop[i].y/=len; 84 } 85 void Mul(cpx *c1,cpx *c2,cpx &a1,cpx &a2,int p,int q) 86 { 87 cpx t1=(c1[p]+!c1[q])*b1,t2=(c1[p]-!c1[q])*b2; 88 cpx t3=(c2[p]+!c2[q])*b1,t4=(c2[p]-!c2[q])*b2; 89 a1=t1*t3+(t1*t4+t2*t3)*b4,a2=t2*t4; 90 } 91 void CDFFT(int *p1,int *p2,int *ans,int len) 92 { 93 register int i; 94 for(i=0;i<len;i++) 95 { 96 a[i].Turn(p1[i]&Bas,p1[i]>>Pow),p1[i]=0; 97 b[i].Turn(p2[i]&Bas,p2[i]>>Pow),p2[i]=0; 98 } 99 Trans(a,len,1),Trans(b,len,1),Mul(a,b,c[0],d[0],0,0); 100 for(i=1;i<len;i++) Mul(a,b,c[i],d[i],i,len-i); 101 Trans(c,len,-1),Trans(d,len,-1); 102 for(i=0;i<len;i++) 103 { 104 long long x1=Roumod(c[i].x),y1=Roumod(c[i].y),x2=Roumod(d[i].x); 105 ans[i]=(((x2<<(Pow<<1))+(y1<<Pow)+x1)%mod+mod)%mod; 106 } 107 } 108 vint Merge(vint v1,vint v2) 109 { 110 register int i; 111 vint ret; ret.clear(); 112 int l1=v1.size()-1,l2=v2.size()-1,len=l1+l2; 113 for(i=0;i<=l1;i++) xx[i]=v1[i]; 114 for(i=0;i<=l2;i++) yy[i]=v2[i]; 115 int lth=1; while(lth<=len) lth<<=1; 116 for(i=0;i<=lth;i++) 117 { 118 rev[i]=(rev[i>>1]>>1)+(i&1)*(lth>>1); 119 ort[i]=(cpx){cos(pai*i/lth),sin(pai*i/lth)}; 120 } 121 CDFFT(xx,yy,ans,lth); 122 for(i=0;i<=len;i++) ret.push_back(ans[i]); 123 return ret; 124 } 125 vint CDQ(int l,int r) 126 { 127 if(l==r) 128 { 129 vint ret; ret.clear(); 130 ret.push_back(1); 131 ret.push_back(odf[l]); 132 return ret; 133 } 134 else 135 { 136 int mid=(l+r)>>1; 137 vint ls=CDQ(l,mid); 138 vint rs=CDQ(mid+1,r); 139 return Merge(ls,rs); 140 } 141 } 142 int main() 143 { 144 register int i; 145 Fread(n),Fread(m); 146 for(i=1;i<=n;i++) Fread(num[i]); 147 Fread(f0),Fread(f1); 148 k2=1ll*(f0+f1)*Qpow(4,mod-2)%mod,k1=(f0-k2+mod)%mod; 149 for(i=1;i<=n;i++) odf[i]=num[i]%2?(mod-1):1; 150 fuc=CDQ(1,n),anss=1ll*fuc[m]*k1%mod; 151 for(i=1;i<=n;i++) odf[i]=Qpow(3,num[i]); 152 fuc=CDQ(1,n),anss=(anss+1ll*fuc[m]*k2%mod)%mod; 153 printf("%d",anss); 154 return 0; 155 }
T3
因为各种原因 ESTR 也被扔进来了
T1 取最长的相同的一段即为答案,证明脑补
T2 循环矩阵的矩阵乘法
不动的矩阵先自己快速幂,然后两个对应乘起来即可,多项式乘法优化到$O(nlog^2 n)$,因为用的是vector所以常数惨不忍睹=。=
1 #pragma GCC optimize(2) 2 #include<cmath> 3 #include<cstdio> 4 #include<cctype> 5 #include<vector> 6 #include<cstring> 7 #include<algorithm> 8 #define vint vector<int> 9 #define vit vector<int> ::iterator 10 using namespace std; 11 const int N=400006,mod=998244353; 12 int n,m,rd,lim,len,G,Gi,Ni; long long t; 13 int a[N],b[N],c[N],rev[N],pw[30][2]; vint aa,bb; 14 void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;} 15 int Qpow(int x,int k) 16 { 17 if(k==1) return x; 18 int tmp=Qpow(x,k/2); 19 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 20 } 21 22 void Pre() 23 { 24 register int i; 25 G=3,Gi=Qpow(G,mod-2); 26 lim=2*n-2,len=1; while(len<=lim) len<<=1; 27 for(int i=0;i<=len;i++) 28 rev[i]=(rev[i>>1]>>1)+(i&1)*(len>>1); 29 for(int i=1;i<=24;i++) 30 { 31 pw[i][0]=Qpow(G,(mod-1)/(1<<i)); 32 pw[i][1]=Qpow(Gi,(mod-1)/(1<<i)); 33 } 34 } 35 void Trans(int *arr,int len,int typ) 36 { 37 register int i,j,k; 38 for(i=0;i<len;i++) 39 if(rev[i]>i) swap(arr[rev[i]],arr[i]); 40 for(i=2;i<=len;i<<=1) 41 { 42 int lth=i>>1,ort=pw[(int)log2(i)][typ==-1]; 43 for(j=0;j<len;j+=i) 44 { 45 int ori=1,tmp; 46 for(k=j;k<j+lth;k++,ori=1ll*ori*ort%mod) 47 { 48 tmp=1ll*ori*arr[k+lth]%mod; 49 arr[k+lth]=(arr[k]-tmp+mod)%mod; 50 arr[k]=(arr[k]+tmp)%mod; 51 } 52 } 53 } 54 if(typ==-1) 55 { 56 int Ni=Qpow(len,mod-2); 57 for(i=0;i<=len;i++) 58 arr[i]=1ll*arr[i]*Ni%mod; 59 } 60 } 61 vint Pmul(vint va,vint vb) 62 { 63 vint ret; ret.clear(); 64 for(int i=0;i<n;i++) a[i]=va[i],b[i]=vb[i]; 65 for(int i=n;i<=len;i++) a[i]=b[i]=0; 66 Trans(a,len,1),Trans(b,len,1); 67 for(int i=0;i<=len;i++) a[i]=1ll*a[i]*b[i]%mod; 68 Trans(a,len,-1); ret.resize(n); 69 for(int i=0;i<2*n-1;i++) Add(ret[i%n],a[i]); 70 return ret; 71 } 72 vint Ppow(vint x,long long k) 73 { 74 if(k==1) return x; 75 vint tmp=Ppow(x,k>>1); 76 return k%2?Pmul(Pmul(tmp,tmp),x):Pmul(tmp,tmp); 77 } 78 int main() 79 { 80 scanf("%d%lld",&n,&t),Pre(); 81 for(int i=0;i<n;i++) scanf("%d",&rd),aa.push_back(rd); 82 for(int i=0;i<n;i++) scanf("%d",&rd),bb.push_back(rd); 83 bb=Ppow(bb,t),reverse(bb.begin(),bb.end()),aa=Pmul(aa,bb); 84 printf("%d ",aa[n-1]); for(int i=0;i<n-1;i++) printf("%d ",aa[i]); 85 return 0; 86 }
T3
若[l,r]中有两个x的倍数,那么一定存在一个a使得a*x和(a+1)*x在[l,r]中,数论分块可过。
可以发现这是有一个分界线的,分界线之后都不合法,也许找出分界线也可以做?
上面fp,显然假的
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 long long l,r,k; 6 int main() 7 { 8 scanf("%lld%lld%lld",&l,&r,&k); 9 if(k==1) printf("%lld",r-l+1),exit(0); 10 long long ll=l-1,res=0; 11 for(long long i=1,j;i<=ll;i=j+1) 12 { 13 j=min(ll/(ll/i),r/(r/i)); 14 if(r/i-ll/i>=2) res+=j-i+1; 15 } 16 printf("%lld",r-l+1+res); 17 return 0; 18 }