总结一下 状态很不对 考场策略出了问题 另外白送的分没要 嘿嘿
六点十几拿题 老师发了题目大意 因为原题目描述不清楚
T1一看 数学题吧 T2一看 半个小时码了暴力 不写了 现在想想真沙雕 T3 我丢 我遇到期望了 老子一定能写出来
我考场上搞了个多次等差数列求和 我很迷 样例也被我卡过去了 但是最后5分 反正这个就是告诉我8 先写完暴力 再去写正解 不然最后暴力分都没有 因为样例会骗你
我们写这个题目 就要提到 luogu青原樱 这个题目了 是一道模拟赛的题目 所以多写比赛 多见题是好的Y
青原樱那个题目的大致意思就是 对于n个位置 然后放置m个花盆 保证两两之间有一个空位，问所有合法的方案数；
那我们怎么考虑求解呢 对于一个长为n的数轴 每两个之间空一个空地 然后 我们将其映射到一个坐标上 我们发现 对于这样一个序列 {am}
我们满足 任意两个 ai+1-ai>=2; 也就是把题目转化为了这样一个问题；
我们考虑 在n个空地里 先放进去m个花盆 至少要有m-1个空位置 然后剩余n-m+1个空位置 对于这n-m+1个空位之中 我们放进去m个 求方案数就是答案
因为 此时我们已经保留了 m-1个位置 我们任意填进去花盆 都会保证 存在空位能够让他和相邻的 相差一个空位 对于两个花盆 我们对他的位置上没有任何要求
因为 我们存在空位使其与空位置交换之后满足相差一个位置 所以说 我们根本不关心 他把花盆放在那里 所以 我们只需要保留了至少m-1个空位置 所以剩下就是求方案了
所以对于那个题目答案就是C（n-m+1,m）*m！，因为题目不要求前后顺序；
T1 就是让你搞一个长为m的数列 然后第一个数是1，最后一个数是n，然后相邻两个数ai+1-ai>=k；
也就是说 上面那个题目就是 k==2 的情况 而这个题目就是k取任意值的方案数
我们依旧类比放空位置 我们不考虑 第一个数和第二个数 所以我们的范围变成了n-2；
我们将其对应到数轴上 然后 我们先留出来（m-1）*（k-1）的空位置 ，然后对于剩下长度为n-2-(m-1)*(k-1）的数轴上 放m-2的数字 因为第一个和最后一个确定了
所以方案数就是C（n-2-（m-1）*（k-1），m-2）；
对于判断奇偶 我们可以用卢卡斯定优化这个过程 对于一个组合数C（n,m）当n&m==m的时候就是奇数；当然 我想到了阶乘分解2的个数 不过是多个log的复杂
很好证明吧 毕竟都是前人的智慧就不讲了了；
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0; T f=1,ch=getchar(); while (!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } int n,T,m,k,ans; inline void dfs(int x,int val) { if(x==m+1) { if(val==n) ans^=1; return ; } for(int i=n-(m-x)*k-val;i>=k;i--) { dfs(x+1,val+i); } } int main() { read(T); while(T--) { read(n); read(m); read(k); dfs(2,1); if(ans) puts("Yes"); else puts("No"); ans=0; } return 0; }
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0; T f=1,ch=getchar(); while (!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } int T,n,m,k; int main() { read(T); while(T--) { read(n); read(m); read(k); if(((n-2-(m-1)*(k-1))&(m-2))==m-2) puts("Yes"); else puts("No"); } return 0; }
T2 写的最快了 不到半个小时LCA 写完 然后测完样例 然后就有60分了 我就没去写 其他四十分，哭辽；
T2大意：给一个 n 个点的树，点有权 ci，边也有权。有 q 次询问， 每次给定 u，询问 f(u) = min v?=u (dist(u, v) + cu − cv) n, q ≤ 2 × 105 .
#include<bits/stdc++.h> using namespace std; const int N=500010; typedef long long ll; template<typename T>inline void read(T &x) { x=0; T f=1,ch=getchar(); while (!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } ll n,m,x,y,v,tot,cost[N],dis[N],d[N],f[N][25],vis[N],lin[N],ans; struct gg { int next,y,v; }a[N<<1]; inline void add(int x,int y,int v) { a[++tot].next=lin[x]; a[tot].v=v; a[tot].y=y; lin[x]=tot; } queue<int> q; inline void bfs(int s) { q.push(s); d[s]=1; dis[s]=0; while(q.size()) { int x=q.front(); q.pop(); for(int i=lin[x];i;i=a[i].next) { int y=a[i].y; if(d[y]) continue; f[y][0]=x; dis[y]=dis[x]+a[i].v; d[y]=d[x]+1; for(int j=1;j<=23;j++) f[y][j]=f[f[y][j-1]][j-1]; q.push(y); } } } inline int lca(int x,int y) { if(d[x]>d[y]) swap(x,y); for(int i=23;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i]; if(x==y) return x; for(int i=23;i>=0;i--) if(f[y][i]!=f[x][i]) y=f[y][i],x=f[x][i]; return f[x][0]; } int main() { freopen("skylines.in","r",stdin); freopen("skylines.out","w",stdout); read(n); int flag=0; for(int i=1;i<=n;i++) { read(cost[i]); } for(int i=1;i<n;i++) { read(x); read(y); read(v); add(x,y,v); add(y,x,v); if(y!=x+1) flag=1; } bfs(1); read(m); while(m--) { read(x); ans=1<<30; for(int i=1;i<=n;i++) { if(i==x) continue; if(ans>dis[x]+dis[i]-2*dis[lca(x,i)]+cost[x]-cost[i]) { ans=dis[x]+dis[i]+cost[x]-cost[i]-2*dis[lca(x,i)]; } } printf("%lld\n",ans); } return 0; }
T3 题目大意：随机生成一个 m + 1 个数的数列，第一个数为 0, 生成第 i个数时，在前 i − 1 个数中等概率选择一个数 k, 则第 i 个数为k + 1。每个数均有一个对应的权值，求数列权值和的期望。
刚看到 我就知道要用到期望的线性/cy 然后我列完了状态 然后 我和迷 这老师发的题目大意 怎么和原题目描述不一样啊
然后我就没写这个题目 后来考完 我读了原题目 题目直接白送了20分 然后爆搜 还有30分
考场上是万万不能弃题的 暴力一定要写 这次是比较深刻的体会吧
所以这次订正 我写了所有的题目的暴力分数
所以总共暴力分30+60+50=140；还是有的 因为大家还有很多没上百qwq
对于这个题目 我们设状态 f[i,j]表示序列的第i个数字是j的概率 也就是第i次玩j章节的概率；
初始化f[1,0]=1表示序章；然后枚举第i次玩 然后枚举章节 然后枚举 是哪一个存档
最后将第i次的概率*题目中给的权值就是期望 第i次玩都有1/i-1的概率选择前面的章节 所以我们预处理出来逆元；
最后还是累和；
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T>inline void read(T &x) { x=0; T f=1,ch=getchar(); while (!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } const ll mod=998244353; const int N=100010; ll ans,cnt,n,m,a[N],now[N],sum[N]; inline void dfs(int x) { if(x==m+2) { ans+=sum[x-1]; if(ans>=mod) ans%=mod; cnt++; return ; } for(int i=1;i<x;++i) { now[x]=now[i]+1;//我当前选择的是哪一章 sum[x]=sum[x-1]+a[now[x]]; dfs(x+1); now[x]=0;//还原现场 sum[x]=0; } } int main() { read(n); read(m); int flag=0; for(int i=2;i<=n+1;++i) { read(a[i]); if(i!=2&&a[i]!=a[i-1]) flag=1; } if(!flag) { printf("%d\n",m*a[2]%mod); return 0; } sum[2]=a[2]; now[1]=1; dfs(2); for(int i=0;;++i) { if((ans+i*mod)%cnt==0) { printf("%lld\n",(ans+i*mod)/cnt); return 0; } } }
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0; T f=1,ch=getchar(); while (!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } typedef long long ll; const ll mod=998244353; ll n,m,a[100005],N[30],E[30],f[30][30]; inline ll mul(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { freopen("kiseki.in","r",stdin); freopen("kiseki.out","w",stdout); read(n); read(m); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=m+1;i++) N[i]=mul(i,mod-2); E[1]=0,f[1][0]=1; for(int i=2;i<=m+1;i++) for(int j=1;j<i;j++) {//枚举玩的章节 for(int k=1;k<i;k++)//枚举随机到的存档 f[i][j]=(f[i][j]+f[k][j-1]*N[i-1]%mod)%mod; E[i]=(E[i]+f[i][j]*a[j]%mod)%mod; } ll ans=0; for(int i=1;i<=m+1;i++) { ans=(ans+E[i])%mod; } cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/Tyouchie/p/11483020.html
