Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 广义斐波那契数递推公式$$f_i=af_{i-1}+bf_{i-2}(\mod p) (p是奇素数)$$ 他的转移矩阵$$ \left[ \begin{matrix} a & b \ 1 & 0 \end{matrix} \right]^n \left[ \begin{matrix} f_{2} \ f_{1} \end{matrix} \right]\mod p= \left[ \begin{matrix} f_{n+2} \ f_{n+1} \end{matrix} \right]$$ 如果存在循环节则存在n使得$$\left[ \begin{matrix} a & b \ 1 & 0 \end{matrix} \right]^n= \left[ \begin ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namethe power of Fibonacci ###descriptionAmy asks Mr. B problem A. Please help Mr. B to solve the following problem.Let Fi be fibonacci number.$F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2}$Given n and m, please calculate$\sum^n_{i=0}{F_i^m}$As the answer might be very large, output it module 1000000000. ###inputThe first and only line contains two integers n, m(1 <= n ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011121314#define I __int128void exgcd(I a,I&x,I b,I&y,I c){ // assert(__gcd(a,b)==c) if(b==0) x=c/a,y=0; else exgcd(b,y,a%b,x,c),y-=a/b*x;}inline bool merge(I x1,I p1,I x2,I p2,I&x,I&p){ I a,b,d=__gcd(p1,p2);// ap1+x1=bp2+x2 a+k(p2/gcd) if((x2-x1)%d!=0) return false; exgcd(p1,a,p2,b,x2-x1); p=p1/d*p2; //lcm x=((a*p1+x1)%p+p)%p;// ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 虚树就是把树上一些节点拿下来重新建树，插入一些lca之类的点，deltree会删除一颗树，但不会删掉他的边,所以要注意边的情况 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// tree 节点0不准使用const int maxn=5e5+5;int head[maxn];// pointint to[maxn*2],ew[maxn*2],nex[maxn*2],tot;// edgeinline void _addedge(int u,int v,int w){to[++tot]=v,ew[tot]=w,nex[tot]=head[u],head[u]=tot;}inline void addedge(int ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011121314151617181920212223242526272829typedef long long ll;struct cp{ static ll p,w; ll x,y;// x+y\sqrt(w) cp(ll x,ll y):x(x),y(y){} cp operator*(cp rhs){ return cp((x*rhs.x+y*rhs.y%p*w)%p,(x*rhs.y+y*rhs.x)%p); }};ll cp::p,cp::w;cp qpow(cp a,ll b){ cp res(1,0); for(;b;b>>=1,a=a*a) if(b&1)res=res*a; return res; ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011//究极读入挂inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(){ char ch=nc();int sum=0; while(!(ch>='0'&&ch<='9'))ch=nc(); while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc(); return sum;
...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 12345678910111213141516171819202122232425262728293031323334353637383940int top,c[N][2],f[N],tim[N],sta[N],rev[N],val[N];void ini(){ for(int i=0;i<=n;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,tim[i]=i,val[i]=2e9; for(int i=n+1;i<=n+m;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,tim[i]=i,val[i]=R[i-n];}inline void pushup(int x){ tim[x]=x; if(val[tim[c[x][0]]]<val[tim[x]]) tim[x]=tim[c ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameexplorer ###descriptionGromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level. There are nvertices and m bidirectional roads in this level, each road is in format (u,v,l,r) , which means that vertex u and v are connected by this road, but the sizes of passers should be in interval [l,r] . Since passers with small size are likely to b ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536const int maxn=1e5+5;int to[maxn<<1],nex[maxn<<1],head[maxn],w[maxn],cnt;void ini(){cnt=-1;for(int i=0;i<=n;i++) head[i]=-1;}void add_edge(int u,int v){to[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;}int dep[maxn],dad[maxn],siz[maxn],son[maxn],chain[maxn],dfn[maxn];//void dfs1(int u,int father){//dfs1(1, ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 霍尔定理推论: 对于一个二分图G<V,E>，若点可以分为两部分N和M,N内部没有边，M同理，S’是N的某个子集(可以为空),f(S’)是与该子集相邻的点集,则他的最大匹配为|N|-max(|S’|-|f(S’)|),