脚本宝典收集整理的这篇文章主要介绍了NOIP模拟56，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
话说， T2 和 T3 的题面好像放反了。
是个原题。。
当时 WindZR 25分钟就码完了，然后我就慌死，写完就开始调，诶，我当时场上不是切了吗，怎么现在打不对了。。
然后我突然发现 sort 的时候 comp 函数压根没有调用，我***。。。
出于内心的各种因素，我造了组 (10^6) 的最大的数据，然后不吸氧 1.5s 吸了 0.9s 险些超时。。
我就有造了一组 (10^6) 的链，然后就愉快的发现 段错误 开大栈空间也无济于事。
于是我就对着这个 段错误 干了 1h 最后实在是不知道哪里错了，果断溜走。
考完之后拿别人的程序一测 都是 段错误 ，我***
那么我们看看 NB 的 WindZR 的 T1 有多少分 ，诶， 15pts
至于题解，请移步 blog
#include<bITs/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e6+10;
int n,ans,dep[N],mxdep[N],fa[N],f[N];
multiset<int> se[N];
vector<int> v[N];
bool comp(int x,int y){return mxdep[x]<;mxdep[y];}
void merge(multiset<int> &x,multiset<int> &y)
{
for(auto it=y.begin();it!=y.end();it++)
x.insert((*it)+1);
}
void DFs(int x)
{
sort(v[x].begin(),v[x].end(),comp);
for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa[x]) dfs(v[x][i]);
for(int i=0;i<v[x].size();i++)
{
int to=v[x][i]; if(to==fa[x]) continue;
for(auto it=se[x].begin();it!=se[x].end();it++)
{
if(se[to].begin()==se[to].end()) break;
int temp=(*it);
if(temp>dep[x]) break;
f[x]+=2*temp;
se[x].erase(it);
se[x].insert((*se[to].begin())+1);
se[to].erase(se[to].begin());
}
merge(se[x],se[to]);
}
if(!v[x].size()) se[x].insert(0);
}
void dfs1(int x)
{
mxdep[x]=dep[x];
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=fa[x])
{
dep[v[x][i]]=dep[x]+1;
dfs1(v[x][i]);
mxdep[x]=max(mxdep[x],mxdep[v[x][i]]);
}
}
signed main()
{
freoPEn("a.in","r",stdin); freopen("a.out","w",stdout);
n=read();
for(int i=2;i<=n;i++) fa[i]=read(),v[fa[i]].push_back(i);
dfs1(1); dfs(1);
for(int i=1;i<=n;i++) ans+=f[i];
for(auto it=se[1].begin();it!=se[1].end();it++) ans+=(*it);
PRintf("%lld",ans);
return 0;
}
按照题解说的运用类似于珂朵莉树的操作，对于区间贡献的 l，r，lr 的系数以及常数项进行维护。
运用求后缀和的后缀数组可以胜任这个区间修改但点查询的操作。
注意珂朵莉树分裂先分裂右端点再分裂左端点，否则右端点的地址会失效。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x;scanf("%lld",&x); return x;
}
const int N=1e6+10,mod=1e9+7,INF=1e9;
int n,q,li[N],ri[N],ans[N];
struct BIT
{
int tre[N<<2];
int lowbit(int x){return x&(-x);}
void add(int x,int val){for(int i=x;i;i-=lowbit(i)) tre[i]=(tre[i]+val)%mod;}
int ask(int x){int sum=0;for(int i=x;i<=n;i+=lowbit(i)) sum=(sum+tre[i])%mod;return sum;}
}l,r,lr,c;
struct Node
{
int l,r,tim;
bool friend operator < (Node x,Node y){return x.l<y.l;}
}s[N];
set<Node> se;
bool comp(Node x,Node y){return x.r<y.r;}
int power(int x,int y){int temp=1;while(y){if(y&1)temp=temp*x%mod;x=x*x%mod;y>>=1;}return temp;}
set<Node>::iterator split(int x)
{
auto it=se.lower_bound((Node){x,0,-1});
if(it!=se.end()&&it->l==x) return it; it--;
int l=it->l,r=it->r,tim=it->tim;
se.erase(it); se.insert((Node){l,x-1,tim});
return se.insert((Node){x,r,tim}).First;
}
void insert(int li,int ri,int tim)
{
auto to=split(ri+1),fro=split(li);
while(fro!=to)
{
int len=fro->r-fro->l+1,t=fro->tim;
lr.add(tim,(mod-len)%mod);
lr.add(t,len);
l.add(tim,(tim-1)*len%mod);
l.add(t,(1-tim+mod)%mod*len%mod);
r.add(tim,(tim+1)*len%mod);
r.add(t,(mod-t-1)*len%mod);
c.add(tim,(1-tim*tim%mod+mod)%mod*len%mod);
c.add(t,(tim+tim*t-t-1+mod)%mod*len%mod);
fro=next(fro); se.erase(prev(fro));
}
se.insert((Node){li,ri,tim});
}
signed main()
{
freopen("b.in","r",stdin); freopen("b.out","w",stdout);
n=read(); q=read();
for(int i=1;i<=n;i++) li[i]=read(),ri[i]=read()-1;
for(int i=1;i<=q;i++) s[i].l=read(),s[i].r=read(),s[i].tim=i;
sort(s+1,s+q+1,comp); se.insert((Node){0,INF,0});
for(int i=1,pos=1;i<=q;i++)
{
while(pos<=s[i].r) insert(li[pos],ri[pos],pos),pos++;
int inv=power((s[i].r-s[i].l+1)*(s[i].r-s[i].l+2)/2%mod,mod-2),sum=0;
sum=(sum+lr.ask(s[i].l)*s[i].l%mod*s[i].r)%mod;
sum=(sum+s[i].r*r.ask(s[i].l))%mod;
sum=(sum+s[i].l*l.ask(s[i].l))%mod;
sum=(sum+c.ask(s[i].l))%mod;
ans[s[i].tim]=sum*inv%mod;
}
for(int i=1;i<=q;i++) printf("%lldn",ans[i]);
return 0;
}
然后后面的 g 的柿子是一个至少形式的二项式反演，别的就没有啥好注意的了。。（又水了一篇 bLOG
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=5e3+10,mod=1e9+7;
int n,m,inv,fac[N<<1],ifac[N<<1],g[N][N],f[N][N];
int C(int x,int y){return fac[y]*ifac[x]%mod*ifac[y-x]%mod;}
int power(int x,int y){int temp=1;while(y){if(y&1)temp=temp*x%mod;x=x*x%mod;y>>=1;}return temp;}
signed main()
{
freopen("c.in","r",stdin); freopen("c.out","w",stdout);
n=read(); m=read();
fac[0]=ifac[0]=1; for(int i=1;i<=n+m;i++) fac[i]=fac[i-1]*i%mod;
ifac[n+m]=power(fac[n+m],mod-2); for(int i=n+m-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=i,base=1;k<=m/j;k++,base*=-1)
(g[i][j]+=base*C(i,k)*C(k,n)%mod*C(n-1,m+n-1-j*k)%mod+mod)%=mod;
for(int i=n;i>=1;i--)
for(int j=1;j<=m/i;j++)
f[i][j]=(f[i+1][j]+g[i][j])%mod;
inv=power(C(n-1,n+m-1),mod-2);
for(int i=1,sum=0;i<=n;i++)
{
for(int j=1;j<=m;j++)
(sum+=f[i][j])%=mod;
printf("%lldn",(sum*inv%mod+i)%mod);
}
return 0;
}
考场上卡时得了 45pts ，尽管有许多强者骗到了 70pts，但是正解好像无人搞出。。
以上是脚本宝典为你收集整理的NOIP模拟56全部内容，希望文章能够帮你解决NOIP模拟56所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。