html模板网站推荐,软文写作什么意思,即时设计怎么做网页,抚顺少儿编程哪家好传送门 明明没参加过却因为点进去结果狂掉\(rating\)…… \(A\) 集合 如果我们记 \[f_k\sum_{i1}^nT^i{n-i\choose k}\] 那么答案显然就是\(f_{k-1}\) 然后就可以开始推倒了 \[ \begin{aligned} f_k \sum_{i1}^nT^i{n-i\choose k}\\ \sum_{i1}^nT^i{n-i-1\choose k}\…传送门 明明没参加过却因为点进去结果狂掉\(rating\)…… \(A\) 集合 如果我们记 \[f_k\sum_{i1}^nT^i{n-i\choose k}\] 那么答案显然就是\(f_{k-1}\) 然后就可以开始推倒了 \[ \begin{aligned} f_k \sum_{i1}^nT^i{n-i\choose k}\\ \sum_{i1}^nT^i{n-i-1\choose k}\sum_{i1}^nT^i{n-i-1\choose k-1}\\ {1\over T}\sum_{i2}^nT^i{n-i\choose k}{1\over T}\sum_{i2}^nT^i{n-i\choose k-1}\\ {1\over T}\left(f_k-T{n-1\choose k}f_{k-1}-T{n-1\choose k-1}\right)\\ {1\over T}\left(f_kf_{k-1}-T{n\choose k}\right)\\ \end{aligned} \] 然后整理一下就可以得到 \[f_k{f_{k-1}-T{n\choose k}\over T-1}\] 边界条件为\(f_0\)显然是个等比数列求和的形式为 \[f_0{T(1-T^n)\over 1-T}\] 直接递推就行了 顺便注意如果\(T1\)那么答案显然是\(1\) //minamoto
#includebits/stdc.h
#define R register
#define fp(i,a,b) for(R int i(a),I(b)1;iI;i)
#define fd(i,a,b) for(R int i(a),I(b)-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
using namespace std;
const int N1e75,P998244353;
inline int add(R int x,R int y){return xyP?xy-P:xy;}
inline int dec(R int x,R int y){return x-y0?x-yP:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){R int res1;for(;y;y1,xmul(x,x))(y1)?resmul(res,x):0;return res;
}
int inv[N],f[N],res,n,k,T,iv;
int main(){
// freopen(testdata.in,r,stdin);scanf(%d%d%d,n,k,T);inv[0]inv[1]1;fp(i,2,k)inv[i]mul(P-P/i,inv[P%i]);if(T1)return puts(1),0;res1,ivksm(T-1,P-2),f[0]1ll*T*(P-iv)%P*(P1-ksm(T,n))%P;fp(i,1,k){res1ll*res*inv[i]%P*(n-i1)%P,f[i]mul(dec(f[i-1],mul(T,res)),iv);}resksm(res,P-2);printf(%d\n,mul(f[k-1],res));return 0;
} \(B\) 染色 点分是个啥我好像已经给忘了…… 要求所有同色点对距离的最小值介于 \([L,R]\) 之间我们可以用最小值大于等于\(L\)的答案减去最小值大于等于\(R1\)的答案 那么考虑形如最小值大于等于\(k1\)的答案怎么算这个的意思就是要求对于\(u\)来说所有到它的距离小于等于\(k\)的点的颜色要和它不同 首先有一个结论如果我们按\(BFS\)序加入点设当前加入的点为\(u\)且对另外两个已经加入的点\(x,y\)满足\(dis(u,x)\leq k\)且\(dis(u,y)\leq k\)则有\(dis(x,y)\leq k\) 证明如果\(u\)到\(x,y\)的两条路径上没有分叉点那么显然成立 如果有分叉点我们记分叉点为\(w\)那么显然\(x,y\)中有一个点是在\(w\)的子树里的不妨假设它为\(x\)。因为是按\(BFS\)序加入所以\(x\)的深度小于\(u\)那么\(dis(x,w)\leq dis(u,w)\)所以\(dis(x,y)\leq dis(u,y)\leq k\) 那么我们按\(BFS\)序加入点对于每个点\(u\)要满足所有和它距离不超过\(k\)的点的颜色互不相同它的颜色也和它们不同 假设和它距离不超过\(k\)的点有\(s\)个那么显然它的方案数就是\(m-s\)其中\(m\)为颜色总数 所以要怎么求和它距离不超过\(k\)的点的个数呢……点分树就可以了……点分树怎么写我已经忘光了所以请看代码自行理解 //minamoto
#includebits/stdc.h
#define R register
#define fp(i,a,b) for(R int i(a),I(b)1;iI;i)
#define fd(i,a,b) for(R int i(a),I(b)-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
templateclass Tinline bool cmin(Ta,const Tb){return ab?ab,1:0;}
templateclass Tinline bool cmax(Ta,const Tb){return ab?ab,1:0;}
using namespace std;
char buf[121],*p1buf,*p2buf;
inline char getc(){return p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1;}
int read(){R int res,f1;R char ch;while((chgetc())9||ch0)(ch-)(f-1);for(resch-0;(chgetc())0ch9;resres*10ch-0);return res*f;
}
const int N2e55,M4e65,L5e75,P1e97;
inline int add(R int x,R int y){return xyP?xy-P:xy;}
inline int dec(R int x,R int y){return x-y0?x-yP:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
struct eg{int v,nx;}e[N1];int head[N],tot;
inline void Add(R int u,R int v){e[tot]{v,head[u]},head[u]tot;}
int pool[L],*ppool;
struct Bit{int n,*c;inline void upd(R int x){for(;xn;xx-x)c[x];}inline int query(R int x){int res0;cmin(x,n);for(;x;x-x-x)resc[x];return res;}
}f[M];int cur;
struct Eg{int nx,dis,sgn;Bit *bi;}E[M];int Head[N],tc;
int sz[N],mx[N],dep[N],vis[N],q[N],fa[N];
int size,rt,n,m,l,r,res1,res2;
void findrt(int u,int fa){sz[u]1,mx[u]0;go(u)if(v!fa!vis[v])findrt(v,u),sz[u]sz[v],cmax(mx[u],sz[v]);cmax(mx[u],size-sz[u]);if(mx[u]mx[rt])rtu;
}
void dfs(int u,int sgn,int d){int h1,t0;dep[u]d,fa[u]0,q[t]u;while(ht){uq[h];go(u)if(!vis[v]v!fa[u])q[t]v,fa[v]u,dep[v]dep[u]1;E[tc]{Head[u],dep[u],sgn,f[cur]},Head[u]tc;}f[cur].cp,f[cur].ndep[q[t]]1,pf[cur].n;
}
void solve(int u){vis[u]1;dfs(u,1,0);int ssize;go(u)if(!vis[v]){dfs(v,-1,1);rt0,size(sz[v]sz[u])?sz[v]:s-sz[u],findrt(v,u);solve(rt);}
}
int main(){
// freopen(testdata.in,r,stdin);nread(),mread(),lread(),rread();for(R int i1,u,v;in;i)uread(),vread(),Add(u,v),Add(v,u);mx[0]n1,rt0,sizen,findrt(1,0),solve(rt);res1res21,memset(vis,0,4*(n1));int h1,t0;q[t]1,vis[1]1;while(ht){int uq[h],s10,s20;for(int iHead[u];i;iE[i].nx){if(E[i].disl)s1E[i].bi-query(l-E[i].dis)*E[i].sgn;if(E[i].disr1)s2E[i].bi-query(r1-E[i].dis)*E[i].sgn;E[i].bi-upd(E[i].dis1);}res1mul(res1,m-s1),res2mul(res2,m-s2);go(u)if(!vis[v])q[t]v,vis[v]1;}printf(%d\n,dec(res1,res2));return 0;
} \(C\) 高尔夫 听说这是个数据结构题而且\(std\)有\(5kb\) 算了咕咕了 转载于:https://www.cnblogs.com/bztMinamoto/p/10640920.html
