NOIP提高组模拟赛14
A. 异或
这种题就是打表，什么性质不性质的不重要
不知道我打表出的式子怎么解释，，
粘一下题解做法吧
"考虑每一位的贡献，从低到高的第\(i\)位会每隔\(2^i\)个数变化一次，于是第$$i位对答案的贡献就是\(\lfloor\frac{i}{2^i}\rfloor\)，
把每一位的贡献加起来即可。"
我的代码
code
#include
using namespace std;
unsigned long long n;
int main(){
scanf("%llu",&n);
unsigned long long base=2;
unsigned long long ans=0;
while(n){
if(n&1)ans+=base-1;
base<<=1;
n>>=1;
}
printf("%llu\n",ans+n);
return 0;
}
B. 赌神
考场理解错了题意，导致送的分都没拿到
考虑\(n=2\)的情况
设\(dp[i][j]\)表示第一种颜色的球剩\(i\)个，第二种颜色的球剩\(j\)个对手中筹码的最大贡献，也可以说是表示你当前有1个筹码，箱子里两种颜色的球分别有\(i,j\)个，你最终能获得多少筹码，这个“1”是单位“1”
由于幕后黑手肯定会按你得筹码最少的情况掉球，所以在最优策略下，不同的掉球情况下最终所能获得的筹码数应该相同
假设你在第一种颜色上押\(x\)个筹码，在第二种颜色上押\(y\)个筹码，有\(x\times dp[i-1][j]=y\times dp[i][j-1]\)又有\(x+y=1\)可以解得\(x\)
容易发现全押一定比不押优(\(dp[i][j]>=1\))，于是有\(dp[i][j]=\frac{2dp[i-1][j]dp[i][j-1]}{dp[i-1][j]+dp[i][j-1]}\)
发现那个系数\(2\)看着不好看，而且可以最后再乘上
所以设\(f[i][j]\times 2^{i+j}=dp[i][j]\)
那么有\(\frac{1}{f[i][j]}=\frac{1}{f[i-1][j]}+\frac{1}{f[i][j-1]}\)
好眼熟，这不是二维图中只能向右上走的方案数吗，直接\((^{i+j}_{\;\;i})\)
答案就是\(\frac{2^{i+j}}{(^{i+j}_{\;\;i})}\)
结论可以扩展到多维情况
code
#include
#include
using namespace std;
const int mod=998244353;
const int maxn=1000005;
int n,x[maxn+15];
long long jc[maxn+15],inv[maxn+15];
long long qpow(long long x,long long y){
long long ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void ycl(){
jc[0]=1;jc[1]=1;inv[0]=1;
for(int i=2;i<=maxn;++i)jc[i]=jc[i-1]*i%mod;
inv[maxn]=qpow(jc[maxn],mod-2);
for(int i=maxn-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
long long get_C(int n,int m){return jc[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
scanf("%d",&n);ycl();
for(int i=1;i<=n;++i)scanf("%d",&x[i]);
long long sum=0;
for(int i=1;i<=n;++i)sum+=x[i];
long long ans = qpow(n,sum);
long long in=1;
for(int i=1;i<=n;++i){
in=in*get_C(sum,x[i])%mod;
sum-=x[i];
}
printf("%lld\n",ans*qpow(in,mod-2)%mod);
return 0;
}
C. 路径
题解不做人，给了个错误式子。。
正解确实要斯特林数，但是还需要换根\(DP\)
有\(x^k=\sum_{i=1}^k \begin{Bmatrix}k\\ i\end{Bmatrix}\times x^{\underline i}\)
\((x+1)^{\underline i}=i\times x^{\underline{i-1}}+x^{\underline i}\)
设\(f[i][j]\)表示\(i\)子树内到\(i\)距离的\(j\)次下降幂之和，\(g[i][j]\)表示\(i\)子树内到\(i\)的父亲距离的\(j\)次下降幂之和
\(f_{i,j}=\sum_{u\in son_i}g_{u,j}\)
\(g_{i,j}=j\times f_{i,j-1}+f_{i,j}\)
看码注释吧。。
code
#include
#include
using namespace std;
const int maxn=1000005;
const int maxk=105;
const int mod=998244353;
const int inv_2=499122177;//2在%mod意义下的逆元
struct edge{
int net,to;
}e[maxn<<1|1];
int head[maxn],tot,n,k;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
int s[maxk][maxk];//斯特林数
int f[maxn][maxk];//f[x][i]x子树内所有点到x的距离的i次下降幂之和
int g[maxn][maxk];//g[x][i]x子树内所有点到x的父亲距离的i次下降幂之和
void pre(){
s[1][1]=1;
for(int i=2;i<=k;++i)
for(int j=1;j<=i;++j)
s[i][j]=(s[i-1][j-1]+1ll*s[i-1][j]*j%mod)%mod;
//第二类斯特林数递推，s(n,m)将n个元素划分为m个非空集合的方案数
//s(n,m)=s(n-1,m-1)+s(n-1,m)*m，前n-1个元素划分为m-1个集合，当前元素只能在第m个集合，前n-1个元素分为m个集合，当前元素可以在任意集合
}
void dfs(int x,int fa){
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;
if(v==fa)continue;
dfs(v,x);
for(int i=0;i<=k;++i){
if(!g[v][i])break;
f[x][i]=(f[x][i]+g[v][i])%mod;
}
}
++f[x][0];
for(int i=k;i;--i)
g[x][i]=(1ll*i*f[x][i-1]%mod+f[x][i])%mod;//x+1的i次下降幂==（x的i-1次下降幂乘以i ）+x的i次下降幂
g[x][0]=f[x][0];
}
int tmp[maxk],sum[maxk];
//换根DP，统计所有点到当前根的贡献，每条路径会被计算两次，最后需要乘2的逆元
void dfs_get(int x,int fa){
for(int i=0;i<=k;++i){
if(!f[x][i])break;
sum[i]=(sum[i]+f[x][i])%mod;
}
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;
if(v==fa)continue;
for(int j=0;j<=k;++j)tmp[j]=(f[x][j]-g[v][j]+mod)%mod;
for(int j=k;j;--j)tmp[j]=(1ll*tmp[j-1]*j%mod+tmp[j])%mod;
for(int j=0;j<=k;++j)f[v][j]=(f[v][j]+tmp[j])%mod;
dfs_get(v,x);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i D. 树
code
#include
#include
#include
#include
using namespace std;
int min(int x,int y){return xmaxdep)maxdep=d[v].dep;
dfs(v);
}
d[x].dfsr=tmp;
}
struct ask{
int l,r,x,y,z,op,pos;
}ak[maxn];
int fk[gm][gm],yk[maxn],pos[maxn],ans[maxn];
void work1(){
for(int mod=1;mod<=len;++mod){
for(int i=1;i<=q;++i){
if(ak[i].op==2){
ans[i]+=fk[pos[ak[i].pos]][d[id[ak[i].pos]].dep%mod]+yk[ak[i].pos];
continue;
}
if(ak[i].x!=mod)continue;
if(pos[ak[i].l]==pos[ak[i].r]){
for(int l=ak[i].l;l<=ak[i].r;++l)
if(ak[i].y==d[id[l]].dep%mod)yk[l]+=ak[i].z;
}else{
int ls=pos[ak[i].l]*len;
for(int l=ak[i].l;l<=ls;++l)
if(ak[i].y==d[id[l]].dep%mod)yk[l]+=ak[i].z;
ls=pos[ak[i].r]*len-len+1;
for(int l=ls;l<=ak[i].r;++l)
if(ak[i].y==d[id[l]].dep%mod)yk[l]+=ak[i].z;
for(int l=pos[ak[i].l]+1;lv[gm];
void add(int l,int r,int v){
cf[l]+=v;cf[r+1]-=v;
ck[pos[l]]+=v;ck[pos[r+1]]-=v;
}
int query(int posi){
int la=0;
for(int l=1;ldr)continue;
v[dep-dl].push_back(ll(ak[i].pos,i));
}
}
for(int i=dl;i<=dr;++i){
int s=v[i-dl].size();
for(int j=0;j