【题解】编程社清明节假期做题记录

2023-11-21 13:40

本文主要是介绍【题解】编程社清明节假期做题记录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

编程社清明节假期做题记录&题解


题目难度顺序个人评价:

T4(KMP,字符串Hash均可做)<T1(线段树,分块均可做)<T5(线段树板子题)<T3(KMP-Next数组应用或字符串Hash)<T6(熟练泼粪(雾))<T2(数论-二项式定理,矩阵快速幂)


文章同步发表于:

  • 博客园

  • Hexo

LaTeX \LaTeX LATEX 没有在 5s 内加载出来请尝试反复刷新缓存。


T1 敌兵布阵

Description

Problem Link

题意简述

N ( N ⩽ 5 × 1 0 4 ) N(N\leqslant5\times 10^4) N(N5×104) 个营地,第 i i i 个营地初始时有 a i a_i ai 个人 ( 1 ⩽ a i ⩽ 50 ) (1\leqslant a_i\leqslant 50) (1ai50),接下来输入若干条命令:

  • Add i j 表示第 i i i 个营地增加 j j j 个人。 ( j ⩽ 30 ) (j\leqslant30) (j30)
  • Sub i j 表示第 i i i 个营地减少 j j j 个人。 ( j ⩽ 30 ) (j\leqslant30) (j30)
  • Query i j 表示询问营地 i ∼ j i\sim j ij 的总人数。
  • End 表示当前数据命令结束。

Solution

简单来说就是单点修改,区间查询。

法一 线段树

Poster Here

这不线段树板子题吗,果然GM只是不想让我们闲着而已。

既然如此,尝试不看以前的代码,手打一遍吧。

法二 分块

Poster There will be a good blog soon…

这不块状链表板子题吗,果然GM只是不想让我们闲着而已。

既然如此,尝试不看以前的代码,手打一遍吧。

人类的本质。。。

Code

线段树

AC on 04/02

#include<cstdio>
#include<cstring>
#define lt p<<1
#define rt lt|1
#define mid (a[p].l+a[p].r>>1)
const int maxn=5e4+5;
int T,n,x,y;
int _a[maxn];
char type[15];
namespace Segment_Tree{struct Structure_of_Segment_Tree{int l,r,sum;}a[maxn<<2];inline void PushUp(int p){a[p].sum=a[lt].sum+a[rt].sum;return;}void Build(int p,int l,int r){a[p].l=l;a[p].r=r;a[p].sum=0;if(l==r){a[p].sum=_a[l];return;}Build(lt,l,mid);Build(rt,mid+1,r);PushUp(p);return;}void Update(int p,int x,int v){if(a[p].l==a[p].r){a[p].sum+=v;return;}if(x<=mid)Update(lt,x,v);else Update(rt,x,v);PushUp(p);return;}int Query(int p,int l,int r){if(l<=a[p].l&&a[p].r<=r)return a[p].sum;int val=0;if(l<=mid)val+=Query(lt,l,r);if(r>mid)val+=Query(rt,l,r);return val;}
}using namespace Segment_Tree;
int main(){scanf("%d",&T);for(int t=1;t<=T;++t){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&_a[i]);Build(1,1,n);printf("Case %d:\n",t);scanf("%s",type+1);while(strcmp(type+1,"End")){scanf("%d%d",&x,&y);switch(type[1]){case 'A':{Update(1,x,y);break;}case 'S':{Update(1,x,-y);break;}case 'Q':{printf("%d\n",Query(1,x,y));break;}default:{puts("114514");break;}}scanf("%s",type+1);}}return 0;
}
分块

AC on 04/03

#include<cmath>
#include<cstdio>
#include<cstring>
const int maxk=233;
const int maxn=5e4+5;
int T,n,x,y;
char type[15];
namespace Block{int k,siz;int sum[maxk];int l[maxk],r[maxk];int a[maxn],pos[maxn];inline void init(void){siz=sqrt(n);k=(n+siz-1)/siz;for(int i=1;i<=k;++i){l[i]=r[i-1]+1;r[i]=l[i]+siz-1;sum[i]=0;}r[k]=n;for(int i=1;i<=n;++i){pos[i]=(i+siz-1)/siz;sum[pos[i]]+=a[i];}return;}inline void Update(int x,int v){a[x]+=v;sum[pos[x]]+=v;return;}inline int Query(int ql,int qr){int res=0;if(pos[ql]==pos[qr]){for(int i=ql;i<=qr;++i)res+=a[i];return res;}for(int i=ql;i<=r[pos[ql]];++i)res+=a[i];for(int i=pos[ql]+1;i<pos[qr];++i)res+=sum[i];for(int i=l[pos[qr]];i<=qr;++i)res+=a[i];return res;}
}using namespace Block;
int main(){scanf("%d",&T);for(int t=1;t<=T;++t){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);init();printf("Case %d:\n",t);scanf("%s",type+1);while(strcmp(type+1,"End")){scanf("%d%d",&x,&y);switch(type[1]){case 'A':{Update(x,y);break;}case 'S':{Update(x,-y);break;}case 'Q':{printf("%d\n",Query(x,y));break;}default:{puts("114514");break;}}scanf("%s",type+1);}}return 0;
}

T2 Yet Another Number Sequence

本篇题解同步发表于 洛谷 。(如果能点个赞那就最好不过了(光速逃

Description

Problem Link

双倍经验

题意简述

F i F_i Fi 表示Fibonacci数列的第 i i i 项,即 F 1 = 1 , F 2 = 2 , F i = F i − 1 + F i − 2 F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2} F1=1,F2=2,Fi=Fi1+Fi2

A i = F i × i k ( k ⩽ 40 ) A_i=F_i\times i^k(k\leqslant 40) Ai=Fi×ik(k40),你的任务是求出其前 n n n 项和 ( n ⩽ 1 0 18 ) m o d 1 0 9 + 7 (n\leqslant 10^{18})\bmod 10^9+7 (n1018)mod109+7 的结果。

Solution

注意到Fibonacci, n ⩽ 1 0 18 n\leqslant 10^{18} n1018 等关键词,明摆着就是一道矩阵加速嘛。

但是,,, ( i − 1 ) k (i-1)^k (i1)k 怎么转移到 i k i^k ik 呢?

BDFS了一大堆后,发现了方法:二项式定理。

k k k 那么小,那你干脆把 ( i − 1 ) 1 , ( i − 1 ) 2 , ( i − 1 ) 3 , ⋯ , ( i − 1 ) k (i-1)^1,(i-1)^2,(i-1)^3,\cdots,(i-1)^k (i1)1,(i1)2,(i1)3,,(i1)k 丢到初始矩阵里去不就行了?

顺便还得把 i 1 , i 2 , i 3 , ⋯ , i k i^1,i^2,i^3,\cdots,i^k i1,i2,i3,,ik 丢进去,然后 ( i − 1 ) x (i-1)^x (i1)x 就可以直接转换成 i x i^x ix

那么 i x i^x ix 也得转换为 ( i + 1 ) x (i+1)^x (i+1)x,所以关键在于 i x i^x ix 怎么转换为 ( i + 1 ) x (i+1)^x (i+1)x

  • 那这不是又回到原问题上了吗!

  • 咱不要急,先慢慢看

经过作者一阵乱搞,发现矩阵乘法是处理不了 A i A_i Ai 的。

所以只能把矩阵里的 i 1 , i 2 , ⋯ , i k i^1,i^2,\cdots,i^k i1,i2,,ik 都乘上一个 F i F_i Fi 来充数。

那么我们看一看 F i + 1 × ( i + 1 ) k F_{i+1}\times(i+1)^k Fi+1×(i+1)k 是怎么得到的:
F i + 1 × ( i + 1 ) k = ( F i − 1 + F i ) × ( i + 1 ) k = F i − 1 × ( i + 1 ) k + F i × ( i + 1 ) k = F i − 1 × [ ( i − 1 ) + 2 ] k + F i × [ ( i ) + 1 ] k \begin{aligned} F_{i+1}\times(i+1)^k&=(F_{i-1}+F_i)\times(i+1)^k\\ &=F_{i-1}\times(i+1)^k+F_i\times(i+1)^k\\ &=F_{i-1}\times[(i-1)+2]^k+F_i\times[(i)+1]^k \end{aligned} Fi+1×(i+1)k=(Fi1+Fi)×(i+1)k=Fi1×(i+1)k+Fi×(i+1)k=Fi1×[(i1)+2]k+Fi×[(i)+1]k
是时候亮出二项式定理了!

众所周知,二项式定理是一个酱紫的东西:
( x + y ) k = ∑ i = 0 k C k i x i y k − i (x+y)^k=\sum\limits_{i=0}^kC_k^ix^iy^{k-i} (x+y)k=i=0kCkixiyki
代入到 [ ( i − 1 ) + 2 ] k [(i-1)+2]^k [(i1)+2]k 中来,就是:
[ ( i − 1 ) + 2 ] x = ∑ j = 0 x C x j ( i − 1 ) j 2 x − j [(i-1)+2]^x=\sum\limits_{j=0}^xC_x^j(i-1)^j2^{x-j} [(i1)+2]x=j=0xCxj(i1)j2xj
而我们刚好有 ( i − 1 ) j (i-1)^j (i1)j

C x j × 2 x − j C_x^j\times2^{x-j} Cxj×2xj 就是 ( i − 1 ) j (i-1)^j (i1)j 在加速矩阵里对应的系数。

又代入到 [ ( i ) + 1 ] x [(i)+1]^x [(i)+1]x 中,得:
[ ( i ) + 1 ] x = ∑ j = 0 x C x j i j [(i)+1]^x=\sum\limits_{j=0}^xC_x^ji^j [(i)+1]x=j=0xCxjij
挺巧的,我们也有 i j i^j ij

C x j C_x^j Cxj 就是 i j i^j ij 在加速矩阵中对应的系数。

S x = ∑ i = 1 x A i S_x=\sum\limits_{i=1}^xA_i Sx=i=1xAi

那么初始矩阵就长这样:
[ F 1 , F 2 , S 1 , F 1 × 1 1 , F 1 × 1 2 , ⋯ , F 1 × 1 k , F 2 × 2 1 , F 2 × 2 2 , ⋯ , F 2 × 2 k ] [F_1,F_2,S_1,F_1\times1^1,F_1\times 1^2,\cdots,F_1\times1^k,F_2\times2^1,F_2\times2^2,\cdots,F_2\times2^k] [F1,F2,S1,F1×11,F1×12,,F1×1k,F2×21,F2×22,,F2×2k]
转移一步后长这样:
[ F 2 , F 3 , S 2 , F 2 × 2 1 , F 2 × 2 2 , ⋯ , F 2 × 2 k , F 3 × 3 1 , F 3 × 3 2 , ⋯ , F 3 × 3 k ] [F_2,F_3,S_2,F_2\times2^1,F_2\times2^2,\cdots,F_2\times2^k,F_3\times3^1,F_3\times3^2,\cdots,F_3\times3^k] [F2,F3,S2,F2×21,F2×22,,F2×2k,F3×31,F3×32,,F3×3k]
转移 n − 1 n-1 n1 步后的最终矩阵长这样:
[ F n , F n + 1 , S n , F n × n 1 , F n × n 2 , ⋯ , F n × n k , F n + 1 × ( n + 1 ) 1 , F n + 1 × ( n + 1 ) 2 , ⋯ , F n + 1 × ( n + 1 ) k ] [F_n,F_{n+1},S_n,F_n\times n^1,F_n\times n^2,\cdots,F_n\times n^k,F_{n+1}\times(n+1)^1,F_{n+1}\times(n+1)^2,\cdots,F_{n+1}\times(n+1)^k] [Fn,Fn+1,Sn,Fn×n1,Fn×n2,,Fn×nk,Fn+1×(n+1)1,Fn+1×(n+1)2,,Fn+1×(n+1)k]
加速矩阵长这样:
[ F i F i + 1 S i F i × i 1 F i × i 2 ⋯ F i × i k F i + 1 × ( i + 1 ) 1 F i + 1 × ( i + 1 ) 2 ⋯ F i + 1 × ( i + 1 ) k F i − 1 ( × ( i − 1 ) 0 ) 0 1 0 0 0 ⋯ 0 2 1 − 0 × C 1 0 = 2 2 2 − 0 × C 2 0 = 4 ⋯ 2 k − 0 × C k 0 F i ( × i 0 ) 1 1 0 0 0 ⋯ 0 C 1 0 = 1 C 2 0 = 1 ⋯ C k 0 S i − 1 0 0 1 0 0 ⋯ 0 0 0 ⋯ 0 F i − 1 × ( i − 1 ) 1 0 0 0 0 0 ⋯ 0 2 1 − 1 × C 1 1 = 1 2 2 − 1 × C 2 1 = 4 ⋯ 2 k − 1 × C k 1 F i − 1 × ( i − 1 ) 2 0 0 0 0 0 ⋯ 0 0 2 2 − 2 × C 2 2 = 1 ⋯ 2 k − 2 × C k 2 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋯ ⋮ F i − 1 × ( i − 1 ) k 0 0 0 0 0 ⋯ 0 0 0 ⋯ 2 k − k × C k k F i × i 1 0 0 0 1 0 ⋯ 0 C 1 1 = 1 C 2 1 = 2 ⋯ C k 1 F i × i 2 0 0 0 0 1 ⋯ 0 0 C 2 2 = 1 ⋯ C k 2 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋯ ⋮ F i × i k 0 0 1 0 0 ⋯ 0 0 0 ⋯ C k k ] \begin{bmatrix} &F_i&F_{i+1}&S_i&F_i\times i^1&F_i\times i^2&\cdots&F_i\times i^k&F_{i+1}\times(i+1)^1&F_{i+1}\times(i+1)^2&\cdots&F_{i+1}\times(i+1)^k \\ F_{i-1}(\times(i-1)^0)&0&1&0&0&0&\cdots&0&2^{1-0}\times C_1^0=2&2^{2-0}\times C_2^0=4&\cdots&2^{k-0}\times C_k^0\\ F_{i}(\times i^0)&1&1&0&0&0&\cdots&0&C_1^0=1&C_2^0=1&\cdots&C_k^0\\ S_{i-1}&0&0&1&0&0&\cdots&0&0&0&\cdots&0\\ F_{i-1}\times(i-1)^1&0&0&0&0&0&\cdots&0&2^{1-1}\times C_1^1=1&2^{2-1}\times C_2^1=4&\cdots&2^{k-1}\times C_k^1\\ F_{i-1}\times(i-1)^2&0&0&0&0&0&\cdots&0&0&2^{2-2}\times C_2^2=1&\cdots&2^{k-2}\times C_k^2\\ \cdots&\vdots&\vdots&\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ F_{i-1}\times(i-1)^k&0&0&0&0&0&\cdots&0&0&0&\cdots&2^{k-k}\times C_k^k\\ F_i\times i^1&0&0&0&1&0&\cdots&0&C_1^1=1&C_2^1=2&\cdots&C_k^1\\ F_i \times i^2&0&0&0&0&1&\cdots&0&0&C_2^2=1&\cdots&C_k^2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ F_i\times i^k&0&0&1&0&0&\cdots&0&0&0&\cdots&C_k^k \end{bmatrix} Fi1(×(i1)0)Fi(×i0)Si1Fi1×(i1)1Fi1×(i1)2Fi1×(i1)kFi×i1Fi×i2Fi×ikFi010000000Fi+1110000000Si001000001Fi×i1000000100Fi×i2000000010Fi×ik000000000Fi+1×(i+1)1210×C10=2C10=10211×C11=100C11=100Fi+1×(i+1)2220×C20=4C20=10221×C21=4222×C22=10C21=2C22=10Fi+1×(i+1)k2k0×Ck0Ck002k1×Ck12k2×Ck22kk×CkkCk1Ck2Ckk

(这个 LaTeX \LaTeX LATEX 是给人打的吗。。。)

好了,除了初始化麻烦点,代码还是比较简单的。

Code

时间复杂度 O ( \mathcal O( O(能过 ) ) )

感谢@w23c3c3大巨佬让我逃离了手推 k = 40 k=40 k=40 大数据然后真·清明节快乐的厄运。

#include<cstdio>
#include<cstring>
#define int long long
const int mod=1e9+7;
const int maxn=105;
struct Matrix{int n,m;int c[maxn][maxn]; Matrix(int N=0,int M=0){n=N,m=M;memset(c,0,sizeof(c));}Matrix operator*(const Matrix a)const{int l=n,r=a.m;Matrix x=Matrix(l,r);for(int i=1;i<=l;++i){for(int j=1;j<=r;++j){for(int k=1;k<=m;++k){x.c[i][j]+=c[i][k]*a.c[k][j];x.c[i][j]%=mod;}}}return x;}
}A,B;
int n,k,x=4;
int f[45][45]; 
Matrix pow(Matrix&x,int b){Matrix ans=Matrix(x.n,x.m);for(int i=1;i<=x.m;++i)ans.c[i][i]=1;while(b){if(b&1)ans=x*ans;x=x*x;b>>=1;}return ans;
}
inline void init(void){f[0][0]=1;for(int i=1;i<=k;++i){f[i][0]=1;for(int j=1;j<=i;++j)f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;}return;
}
signed main(){scanf("%lld%lld",&n,&k);init();A=Matrix(1,3+(k<<1));A.c[1][1]=1;A.c[1][2]=2;A.c[1][3]=1;for(int i=1;i<=k;++i){A.c[1][3+i]=1;A.c[1][k+3+i]=x%mod;x<<=1;}B=Matrix(3+(k<<1),3+(k<<1));B.c[2][1]=1;B.c[1][2]=B.c[2][2]=1;B.c[3][3]=B.c[3+(k<<1)][3]=1;for(int i=1;i<=k;++i){B.c[1][i+k+3]=(1ll<<i)%mod;B.c[3+k+i][3+i]=1;B.c[2][3+i+k]=1;}for(int i=1;i<=k;++i){for(int j=i;j<=k;++j){B.c[3+i][3+k+j]=(((1ll<<j-i)%mod)*f[j][i])%mod;B.c[3+k+i][3+k+j]=f[j][i];}}A=A*pow(B,n-1);printf("%lld",A.c[1][3]);return 0;
}

T3 JM的荧光棒工厂

Description

Problem Link

题意简述

给定字符串 S ( 1 ⩽ ∣ S ∣ ⩽ 2 × 1 0 5 ) S(1\leqslant|S|\leqslant2\times10^5) S(1S2×105),求出所有既是 S S S 的前缀,又是 S S S 的后缀的子串长度。

Solution

法一 KMP

主要考察 KMP Next 数组的理解和应用。

经典KMP题了。

法二 字符串Hash

因为某种不可描述的原因,咕掉了 我自裁qwq

枚举一下 1 ∼ ∣ S ∣ − 1 1\sim |S|-1 1S1 的所有长度,比对这个长度的前缀和后缀的Hash值是否相等即可。

Code

KMP

AC on 04/03

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using std::sort;
const int maxn=2e5+5;
int tot,len;
char S[maxn];
int ans[maxn];
int Next[maxn];
void get_Next(void){int i=0,j=-1;Next[0]=-1;while(i<len){if(j==-1||S[i]==S[j]){i++;j++;Next[i]=j;}else j=Next[j];}return;
}
signed main(){scanf("%s",S);len=strlen(S);get_Next();while(len>0){ans[++tot]=len;len=Next[len];}printf("%lld\n",tot-1);sort(ans+1,ans+tot+1);for(int i=1;i<tot;++i)printf("%lld ",ans[i]);return 0;
}
字符串Hash

AC on 04/05

#include<cstdio>
#include<cstring>
#define int unsigned long long
const int p=13331;
const int maxn=2e5+5;
int tot,len;
char s[maxn];
int ans[maxn];
int __HaSh__[maxn];
inline int qkp(int ds,int zs){int ans=1;while(zs){if(zs&1)ans*=ds;ds*=ds;zs>>=1;}return ans;
}
inline int Get_Hash(int l,int r){int q=qkp(p,r-l+1);return __HaSh__[r]-__HaSh__[l-1]*q;
}
signed main(){scanf("%s",s+1);len=strlen(s+1);for(int i=1;i<=len;++i)__HaSh__[i]=__HaSh__[i-1]*p+s[i];for(int i=1;i<len;++i){if(Get_Hash(1,i)==Get_Hash(len-i+1,len))ans[++tot]=i;}printf("%llu\n",tot);for(int i=1;i<=tot;++i)printf("%llu ",ans[i]);return 0;
}

T4 剪花布条

Description

Problem Link

双倍经验

题意简述

给定两个字符串 S , M ( ∣ S ∣ , ∣ M ∣ ⩽ 1000 ) S,M(|S|,|M|\leqslant1000) S,M(S,M1000),求 S S S 中最多有多少个互不重叠的 M M M

Solution

法一 KMP

又是一道KMP板子题。只是在KMP匹配成功时 j j j 要从 0 0 0 开始从头匹配。

法二 字符串Hash

同样也很板,直接模拟一遍匹配过程即可。但是常数与KMP相比稍大。

Code

KMP

AC on 04/03

#include<cstdio>
#include<cstring>
const int maxn=1005;
int Next[maxn];
int ans,ALen,BLen;
char S[maxn],M[maxn];
void KMP(char *A,char *B){ans=0;int i=0,j=-1;Next[0]=-1;BLen=strlen(B);while(i<BLen){if(j==-1||B[i]==B[j]){i++;j++;Next[i]=j;}else j=Next[j];}i=0,j=0;while(i<ALen&&j<BLen){if(j==-1||A[i]==B[j]){i++;j++;}else j=Next[j];if(j==BLen){ans++;j=0;}}return;
}
int main(){while(~scanf("%s",S)){if((ALen=strlen(S))==1){if(S[0]=='#')return 0;}scanf("%s",M);KMP(S,M);printf("%d\n",ans);}return 0;
}
字符串Hash

AC on 04/05

#include<cstdio>
#include<cstring>
#define int unsigned long long
const int p=13331;
const int maxn=1005;
int __HaSh__[maxn];
char s[maxn],m[maxn];
int lens,lenm,ans,now,hamh;
inline int qkp(int ds,int zs){int ans=1;while(zs){if(zs&1)ans*=ds;ds*=ds;zs>>=1;}return ans;
}
inline int Get_Hash(int l,int r){int q=qkp(p,r-l+1);return __HaSh__[r]-__HaSh__[l-1]*q;
}
signed main(){while(~scanf("%s",s+1)){ans=hamh=0;if((lens=strlen(s+1))==1){if(s[1]=='#')return 0;}scanf("%s",m+1);lenm=strlen(m+1);for(int i=1;i<=lens;++i)__HaSh__[i]=__HaSh__[i-1]*p+s[i];for(int i=1;i<=lenm;++i)hamh=hamh*p+m[i];now=1;while(now<=lens-lenm+1){if(Get_Hash(now,now+lenm-1)==hamh){ans++;now+=lenm;}else now++;}printf("%llu\n",ans);}return 0;
}

T5 函数

Description

Problem Link

题意简述

Q Q Q 个询问 ( 1 ⩽ Q ⩽ 1 0 5 ) (1\leqslant Q\leqslant 10^5) (1Q105),对于每个测试点,给定 m o d ( 1 ⩽ m o d ⩽ 1 0 14 ) mod(1\leqslant mod\leqslant 10^{14}) mod(1mod1014),对于每个询问,给定 n , r ( 1 ⩽ r ⩽ n ⩽ 1 0 5 ) n,r(1\leqslant r\leqslant n\leqslant 10^5) n,r(1rn105),其中 m o d mod mod 不一定是质数,求 C n r × ( n − r ) ! m o d m o d C_n^r\times(n-r)!\bmod mod Cnr×(nr)!modmod

Solution

m o d mod mod 是质数,可以用逆元。(虽然我不会)

但是,这里的 m o d mod mod 不一定是质数了,我们就要想办法避免除法。

开始推式子:
C n r × ( n − r ) ! = n ! r ! ( n − r ) ! × ( n − r ) ! = n ! r ! \begin{aligned} C_n^r\times(n-r)!&=\frac{n!}{r!(n-r)!}\times(n-r)!\\ &=\frac{n!}{r!} \end{aligned} Cnr×(nr)!=r!(nr)!n!×(nr)!=r!n!
此时暴力的时间复杂度为 O ( n Q ) \mathcal O(nQ) O(nQ),要炸。

所以考虑把 1 ∼ 1 0 5 1\sim 10^5 1105 中的连乘值处理出来,然后线段树区间查询 r + 1 ∼ n r+1\sim n r+1n 的连乘。

Code

这道不要脸的题居然要开 __int128 ,差评。

注:int 30pts \text{30pts} 30ptslong long 50pts \text{50pts} 50pts

AC on 04/03

#include<cstdio>
#include<cstring>
#define int __int128
#define lt p<<1
#define rt lt|1
#define mid (a[p].l+a[p].r>>1)
const int maxn=1e5+5;
const int LEN=(1<<20);
int Q,n,mod,r;
namespace Segment_Tree{struct Structure_of_Segment_Tree{int l,r,mul;}a[maxn<<2];inline void PushUp(int p){a[p].mul=(a[lt].mul*a[rt].mul)%mod;return;}void Build(int p,int l,int r){a[p].l=l;a[p].r=r;a[p].mul=1;if(l==r){a[p].mul=l%mod;return;}Build(lt,l,mid);Build(rt,mid+1,r);PushUp(p);return;}int Query(int p,int l,int r){if(l<=a[p].l&&a[p].r<=r)return a[p].mul;int val=1;if(l<=mid)val=Query(lt,l,r);if(r>mid)val=(val*Query(rt,l,r))%mod;return val;}
}using namespace Segment_Tree;
inline int nec(){static char buf[LEN],*p=buf,*e=buf;if(p==e){if((e=buf+fread(buf,1,LEN,stdin))==buf)return EOF;p=buf;}return *p++;
}
inline bool read(int&x){static char neg=0,c=nec();neg=0,x=0;while((c<'0'||c>'9')&&c!='-'){if(c==EOF)return 0;c=nec();}if(c=='-'){neg=1;c=nec();}do{x=x*10+c-'0';}while((c=nec())>='0');if(neg)x=-x;return 1;
}
void print(int x){if(x>9)print(x/10);putchar(x%10+'0');return;
}
signed main(){#ifdef ONLINE_JUDGEfreopen("function.in","r",stdin);freopen("function.out","w",stdout);#endifread(Q);read(mod);Build(1,1,1e5+5);while(Q--){read(n);read(r);print(Query(1,r+1,n));putchar('\n');}return 0;
}

T6 树的统计

Description

Problem Link, and this,this,this,this,this.

题意简述

原题目描述够简了。

Solution

树剖板子题,有手就行,不讲。快来!这里有个人水博客!

Code

AC on 04/03

#include<cstdio>
const int maxn=3e4+5;
const int inf=0x3f3f3f3f;
struct _{int l,r;int mx,sum;
}a[maxn<<2];
char s[15];
int n,q,x,y,tot,cnt;
int to[maxn<<1],nxt[maxn<<1];
int h[maxn],dep[maxn],w[maxn],rk[maxn];
int f[maxn],hvst[maxn],siz[maxn],st[maxn],top[maxn];
void add(int x,int y){to[++tot]=y;nxt[tot]=h[x];h[x]=tot;return;
}
int max(int x,int y){return x>y?x:y;}
void swap(int&x,int&y){if(x==y)return;x^=y^=x^=y;return;
}
void dfs1(int x,int fa){siz[x]=1;int mxsiz=0;for(int i=h[x];i;i=nxt[i]){int v=to[i];if(v==fa)continue;dep[v]=dep[x]+1;f[v]=x;dfs1(v,x);siz[x]+=siz[v];if(siz[v]>mxsiz){mxsiz=siz[v];hvst[x]=v;}}return;
}
void dfs2(int x,int tp){top[x]=tp;st[x]=++cnt;rk[cnt]=x;if(!hvst[x])                           return;dfs2(hvst[x],tp);for(int i=h[x];i;i=nxt[i]){int v=to[i];if(v!=f[x]&&v!=hvst[x])dfs2(v,v); }return;
}
void build(int p,int l,int r){a[p].l=l,a[p].r=r;if(l==r){a[p].mx=a[p].sum=w[rk[l]];return;}int mid=l+r>>1;int lt=p<<1;int rt=lt|1;build(lt,l,mid);build(rt,mid+1,r);a[p].mx=max(a[lt].mx,a[rt].mx);a[p].sum=a[lt].sum+a[rt].sum;return;
}
void Update(int p,int x,int v){if(a[p].l==a[p].r){a[p].sum=a[p].mx=v;return;}int lt=p<<1;int rt=lt|1;int mid=a[p].l+a[p].r>>1;if(x<=mid)Update(lt,x,v);else Update(rt,x,v);a[p].mx=max(a[lt].mx,a[rt].mx);a[p].sum=a[lt].sum+a[rt].sum;return;
}
int QueryMax(int p,int l,int r){if(l<=a[p].l&&r>=a[p].r)return a[p].mx;int val=-inf;int mid=a[p].l+a[p].r>>1;if(l<=mid)val=max(val,QueryMax(p<<1,l,r));if(r>mid)val=max(val,QueryMax((p<<1)|1,l,r));return val;
}
int QuerySum(int p,int l,int r){if(l<=a[p].l&&r>=a[p].r)return a[p].sum;int val=0;int mid=a[p].l+a[p].r>>1;if(l<=mid)val+=QuerySum(p<<1,l,r);if(r>mid)val+=QuerySum((p<<1)|1,l,r);return val;
}
int QueryMaxPath(int x,int y){int res=-inf;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);res=max(res,QueryMax(1,st[top[x]],st[x]));x=f[top[x]];}if(dep[x]>dep[y])swap(x,y);res=max(res,QueryMax(1,st[x],st[y]));return res;
}
int QuerySumPath(int x,int y){int res=0;while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y);res+=QuerySum(1,st[top[x]],st[x]);x=f[top[x]];}if(dep[x]>dep[y])swap(x,y);res+=QuerySum(1,st[x],st[y]);return res;
}
int main(){dep[1]=1;scanf("%d",&n);for(int i=1;i<n;++i){ scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;++i)scanf("%d",&w[i]);dfs1(1,-1);dfs2(1,1);build(1,1,n);scanf("%d",&q);while(q--){scanf("%s%d%d",s+1,&x,&y);if(s[1]=='C')Update(1,st[x],y);else if(s[2]=='M')printf("%d\n",QueryMaxPath(x,y));else printf("%d\n",QuerySumPath(x,y));}return 0;
}

end.

这篇关于【题解】编程社清明节假期做题记录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/402675

相关文章

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中