异或
别笑我，考场上打的数位dp ? ,而且(1<<i)少写了 (1ll<<i) 大点炸了，挂了 40
考虑正解：很明显，产生贡献的一定是一段连续的1
那么直接假设 第 i 为 0 现在只需要算出 <n-(1<<i)+1 的数的个数，要求 i 位之前都为 0
直接数位 dp
题解做法： 把 dp 换成结论: 考虑每一位的贡献，从低到高的第 位会每隔 个数变化一次，于是第 位对答案的贡献就是 allans ，把每一位的贡献加起来即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}int p[100],op,alllim;
int f[100][2],qwq;//数量和
int yg=0;
int ask(int pos,int lim){
if(pos<=op){return f[pos][lim]=1;}
if(!lim&&f[pos][lim]) {return f[pos][lim];}
int maxx=1,ans=0;
if(lim) maxx=p[pos];
for(int i=0;i<=maxx;i++){
ans+=ask(pos-1,lim&&i==maxx);
}if(!lim) f[pos][lim]=ans;
return ans;
}
void pre(int x){
int cnt=0;
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
while(x){
p[cnt++]=x%2;
x/=2;
}cnt--;
qwq=ask(cnt,1);
}
signed main(){
// freopen("date.txt","r",stdin);
int n=read();
if(n&1) alllim=n-2;
else alllim=n-1;
for(int i=1;i<=62;i++){//第i位是0
int lm=alllim-((1ll<<i)-1);//剩余位数 的 lm限制
if(lm<0) break;
op=i;//<=op 只选0
pre(lm);
yg=yg+(i+1)*qwq;
}
yg+=(n+1)/2;
cout<<yg<<endl;
}
赌神
考虑样例 ，发现按比例分才能避免被背刺，发现幕后黑手如果一直让一个减小，最后的期望实际上是会不降的，所以幕后黑手每次一定拿出最多的一个球
直接优先队列模拟一下
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}int n,mod=998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int qpow(int xx,int yy){int zz=1;
while(yy){
if(yy&1) zz=mul(zz,xx);
xx=mul(xx,xx);
yy>>=1;
}return zz;
}inline void work(){
int x=read();
cout<<qpow(n,x)<<endl;
return;
}priority_queue<int> q;
int S,now;
signed main(){
n=read();
if(n==1) {
work(); return 0;
}else{
now=1;
for(int i=1;i<=n;i++){
int x=read();
if(x) q.push(x);
S+=x;
}int m=S;
for(int i=1;i<=m;i++){
int x=q.top(); q.pop();
int xx=mul(now,mul(x,qpow(S,mod-2)));
now=mul(xx,n);
S--;
if(x-1) q.push(x-1);
} printf("%lld\n",now);
}
return 0;
}
路径
公式打不出来，题解在我草稿纸上
还有就是，为什么正解好像只有我卡了T3的常数 ?
考场上常数被卡了，本地 2.3 秒的 sub4 oj上 T 了 ?
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define v e[i].to
#define N 1000005
#define pb push_back
#define re register int
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}
const int mod=998244353;
int n,k;
struct Edge{
int to,nex;
}e[N<<2];
int h[N],tot;
void in(int x,int y){
e[++tot]=(Edge){y,h[x]}; h[x]=tot;
}
int er[105],ans;
inline int add(int x,int y){if(x+y>=mod) return x+y-mod; return x+y;}
inline int del(int x,int y){if(x>y) return x-y; return (x-y+mod)%mod;}
inline int mul(int x,int y){if(1ll*x*y>=mod) return 1ll*x*y%mod; return x*y;}
int dn[N][105],up[N][105],S[105][105];
inline int qpow(int xx,int yy){int zz=1;
while(yy){
if(yy&1) zz=mul(zz,xx);
xx=mul(xx,xx);
yy>>=1;
}return zz;
}void dfs(int u,int fa){
dn[u][0]=1;
for(re i=h[u];i;i=e[i].nex){
if(v==fa) continue;
dfs(v,u);
dn[u][0]=add(dn[u][0],dn[v][0]);
for(re j=1;j<=k;j++) dn[u][j]=add(dn[u][j],add(dn[v][j],dn[v][j-1]));
}
}void dfs2(int u,int fa){
if(fa){
up[u][0]=add(up[fa][0],del(dn[fa][0],dn[u][0]));
up[u][1]=add(up[fa][1],add(up[fa][0],add(dn[fa][1],dn[fa][0])));
up[u][1]=del(up[u][1],add(dn[u][1],mul(2,dn[u][0])));
for(re i=2;i<=k;i++){
up[u][i]=add(up[u][i],up[fa][i]);
up[u][i]=add(up[u][i],up[fa][i-1]);
up[u][i]=add(up[u][i],dn[fa][i]);
up[u][i]=add(up[u][i],dn[fa][i-1]);
up[u][i]=del(up[u][i],dn[u][i]);
up[u][i]=del(up[u][i],mul(2,dn[u][i-1]));
up[u][i]=del(up[u][i],dn[u][i-2]);
}
}
for(re i=h[u];i;i=e[i].nex)if(v!=fa) dfs2(v,u);
}
signed main(){
// freopen("date.txt","r",stdin);
n=read(),k=read();
for(int i=1;i<n;i++) {
int x=read(),y=read();
in(x,y); in(y,x);
}
dfs(1,0);
dfs2(1,0);
er[0]=1; for(re i=1;i<=k;i++) er[i]=mul(er[i-1],i);
S[0][0]=1;
for(re i=1;i<=k;i++)
for(re j=1;j<=k;j++)
S[i][j]=add(S[i-1][j-1],mul(j,S[i-1][j]));
for(re i=1;i<=n;i++){
for(re j=0;j<=k;j++){
ans=add(ans,mul(er[j],mul(S[k][j],add(up[i][j],dn[i][j]))));
}
}ans=mul(ans,qpow(2,mod-2));
printf("%lld\n",ans);
return 0;
}
树
首先对于每一次修改可以转化为在 u 的子树内dep[v]%x==(dep[u]+y)%x的点上 加权 ，为了方便，我们转化为
lp : dfn[u]
rp : dfn[u]+siz[u]-1;
y : (dep[u]+y)%x
问题转化为 将i 在[lp,rp]上，dep[dfs[i]]%x=y 的加一个值
这种不是很好处理，考虑优化暴力
首先，我们分块处理 dfs 序
然后，对于x根号分支
对于 x<=sqrt(n)
我们发现 模数< sqrt(n) ，所以对于散块我们直接暴力扫
对于整块 i ,我们直接记X[i][j][k]表示，第i个块内%j=k的权的和
修改时O(1)的，查询时，我们直接枚举 j ，可得k=dep[u]%j，直接加上权
对于x>sqrt(n)
我们发现每次能产生的影响的 dep 不超过 sqrt(n) 个
所以我们对于散块依旧扫一遍
对于整块，我们记 Y[i][k] 表示i块里面 深度为 j 的权
令lpos为左端点所在块， rpos为右端点所在块
对于[lpos+1,rpos-1]整块差分 ，具体的我们枚举i*x+y将 Y[pos[lp]+1][i*x+y]+=z,Y[pos[rp]][i*x+y]-=z;
查询的时候直接对于块 前缀和 ，时间复杂度 O(sqrt(n))
但是要卡空间，所以要调整块长
代码其实很短
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define v e[u][i]
#define N 300005
#define B 105
#define pb push_back
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}vector<int> e[N];
int dep[N],dfn[N],a[N],dfs[N],l[N],r[N],p[N],siz[N],X[B][550][550],Y[B][N],n,QQ;//每个询问的答案
void ds(int u,int f){
dfn[u]=++dfn[0]; siz[u]=1; dfs[dfn[0]]=u; dep[u]=dep[f]+1;
for(int i=0;i<e[u].size();i++)if(v!=f) ds(v,u),siz[u]+=siz[v];
}void cha(int lp,int rp,int x,int y,int z){for(int i=lp;i<=rp;i++) if(dep[dfs[i]]%x==y) a[i]+=z;}
void upd(int lp,int rp,int x,int y,int z){
int lpos=p[lp],rpos=p[rp];
if(lpos==rpos){cha(lp,rp,x,y,z);return;}
cha(lp,r[lpos],x,y,z); cha(l[rpos],rp,x,y,z);
for(int i=lpos+1;i<=rpos-1;i++) X[i][x][y]+=z;
}void lm(int lp,int rp,int x,int y,int z){
int lpos=p[lp],rpos=p[rp];
if(lpos==rpos){cha(lp,rp,x,y,z);return;}
cha(lp,r[lpos],x,y,z); cha(l[rpos],rp,x,y,z);
for(int j=0;j*x+y<=n;j++) Y[lpos+1][j*x+y]+=z,Y[rpos][j*x+y]-=z;
}signed main(){
n=read(),QQ=read(); for(int i=1;i<n;i++){int x=read(),y=read();e[x].pb(y); e[y].pb(x);}
ds(1,0); int len=3000,tmp=n/len;
for(int i=1;i<=n/len;++i) {l[i]=r[i-1]+1; r[i]=i*len;}
if(r[tmp]<n){++tmp; l[tmp]=r[tmp-1]+1; r[tmp]=n;}
for(int i=1;i<=tmp;++i) for(int j=l[i];j<=r[i];j++) p[j]=i;
for(int qq=1;qq<=QQ;qq++){ int opt=read();
if(opt==1){
int u=read(),x=read(),y=read(),z=read();
y=(dep[u]+y)%x;
if(x<=sqrt(u)) upd(dfn[u],dfn[u]+siz[u]-1,x,y,z);
else{lm(dfn[u],dfn[u]+siz[u]-1,x,y,z);}
}else{
int u=read(),ans=a[dfn[u]],dp=dep[u];
for(int i=1;i<=p[dfn[u]];i++) ans+=Y[i][dp];
for(int now=1;now<=sqrt(n);now++) ans+=X[p[dfn[u]]][now][dp%now];
printf("%d\n",ans);
}
}
}