191009NOI模拟题解

T1:
给你一个长为n的数组，下标从0开始，每个数都是0…9，你需要回答Q个询问：给出li,ri，求区间[li,ri]中所有数的乘积模10的结果。
小A轻松地解决了这道题，现在她想知道：给出n,Q,li,ri，以及每组询问的答案ansi，求原数组有多少种不同的情况？
$n,q\le 100$

先用中国剩余定理转化为%2和%5的情况，然后分别统计，最后乘起来
考虑一个点为0的情况，则跨过这个点的区间的答案必须全是0，可以区间DP统计一下
然后其他的情况就用带权并查集统计即可

Code：

#include<bits/stdc++.h>
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
int mo;
inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Dec(int &x,int y){x-=y;if(x<0) x+=mod;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
inline int ksm(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a);return res;}
const int N=105;
struct info{
int l,r,x;
info(){}
info(int _l,int _r,int _x):l(_l),r(_r),x(_x){}
};
int fa[N],val[N];
int get(int x){
if(fa[x]==x) return fa[x];
int f=fa[x];
fa[x]=get(fa[x]);
val[x]=1ll*val[x]*val[f]%mo;
return fa[x];
}
int inv[N];
inline bool Union(int x,int y,int z){
int xx=get(x),yy=get(y);
if(xx!=yy){
fa[xx]=yy;
val[xx]=1ll*val[y]*inv[val[x]]*inv[z]%mo;
return 1;
}
else return 1ll*val[y]*inv[val[x]]%mo==z;
}
int f[N][N],g[N][N];
int dp1(int l,int r,vector<info>v){
if(v.empty()) return ksm(mo-1,r-l+1);
int &tmp=f[l][r];
if(~tmp) return tmp;
for(int i=l-1;i<=r;i++) fa[i]=i,val[i]=1;
for(int i=0;i<v.size();i++){
if(v[i].x==0) return tmp=0;
if(!Union(v[i].l-1,v[i].r,v[i].x)) return tmp=0;
}
int res=0;
for(int i=l-1;i<=r;i++) if(fa[i]==i) ++res;
return res=ksm(mo-1,res-1);
}
int dp2(int l,int r,vector<info>v){
if(v.empty()) return ksm(mo,r-l+1);
int &tmp=g[l][r];
if(~tmp) return tmp;
tmp=dp1(l,r,v);
for(int i=l;i<=r;i++){
int flag=1;vector<info>v1,v2;
for(int j=0;j<v.size();j++){
if(v[j].l<=i && i<=v[j].r) if(v[j].x!=0) flag=0;
if(v[j].r<i) v1.pb(v[j]);
if(v[j].l>i) v2.pb(v[j]);
}
if(!flag) continue;
inc(tmp,mul(dp1(l,i-1,v1),dp2(i+1,r,v2)));
}
return tmp;
}
vector<info>vv;
int l[N],r[N],x[N];
int n,m;
inline void file(){freopen("dist.in","r",stdin);freopen("dist.out","w",stdout);}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++) l[i]=read(),r[i]=read(),x[i]=read();
mo=2;
int ans=1;
memset(f,-1,sizeof(f));memset(g,-1,sizeof(g));
for(int i=1;i<=m;i++) vv.pb(info(l[i]+1,r[i]+1,x[i]%2));
inv[1]=1;
Mul(ans,dp2(1,n,vv));
mo=5;
memset(f,-1,sizeof(f));memset(g,-1,sizeof(g));vv.clear();
for(int i=1;i<=m;i++) vv.pb(info(l[i]+1,r[i]+1,x[i]%5));
for(int i=1;i<=5;i++) inv[i]=i*i*i%5;
Mul(ans,dp2(1,n,vv));
cout<<ans<<endl;
return 0;
}

T2：考虑一张n个点的无向完全图，总共有n∗(n−1)/2条边。每条边有$\frac{p}{10^6}$的概率存在，$1-\frac{p}{10^6}$的概率不存在。
现在等概率在n个点中随机一个，求1号点到它的最短距离（经过的边数）。如果1号点和它不连通，则认为答案是$10^9$。
求期望答案。
$n\le 400$

这种题一般就是按最短路分层，考虑层与层之间的dp
设f[i][j][k]表示第i层，用了j个点，最后一层有k个点的情况，转移枚举下一层的点数l即可做到$n^4$

考虑优化，发现第i层这个限制不必要，可以去掉，但是我们需要一个新的状态表示i这一层。即到达某个状态时距离的期望值
那么我们设两个数组f,e分别表示概率和期望，转移就考虑这一层的点和下一层的点的连通性，下一层的点必须都和这一层中至少一个点连边，且不属于下一层的点不能与这一层连边，再乘个组合数表示选点的方案数，那概率就可以直接转移了
考虑期望的转移，设这一层的点到1号点的距离为dis，则下一层就是dis+1，那么期望就是
$$f[i][j]\ast (dis+1)=f[i][j]\ast \ast dis+f[i][j]=e[i][j]+f[i][j]$$
也可以用期望的线性性证明
因为除了1号点，每个点是等价的，所以我们算一个点的期望，最后乘个n-1即可
算一个点的期望就枚举所有状态，然后考虑在当前状态下这个点连不连最后一层的某一个点，统计一下即可

Code：

#include<bits/stdc++.h>
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 998244353
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Dec(int &x,int y){x-=y;if(x<0) x+=mod;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
inline int ksm(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a);return res;}
const int N=500,INF=1e9;
int n,p;
int fac[N],ifac[N],pw[N];
inline void init_fac(){
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=mul(ifac[i+1],i+1);
}
int p1[N][N],p2[N][N];
inline void init_w(){
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=mul(pw[i-1],p);
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++) p1[i][j]=ksm(dec(1,pw[i]),j);
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++) p2[i][j]=ksm(p,i*j);
}
inline int C(int n,int m){if(n<0 || m<0 || n<m) return 0;return mul(fac[n],mul(ifac[m],ifac[n-m]));}
int ans=0,f[N][N],e[N][N];
inline void file(){freopen("dist.in","r",stdin);freopen("dist.out","w",stdout);}
int main(){
n=read();p=read();p=mul((1e6-p),ksm(1e6,mod-2));
init_fac();init_w();
f[1][1]=1;e[1][1]=0;
for(int i=1;i<=n-1;i++)
for(int j=1;j<=i;j++) if(f[i][j]){
for(int k=1;k<=n-i-1;k++){
int tmp=mul(p1[j][k],mul(p2[j][n-i-k],C(n-i-1,k)));
inc(f[i+k][k],mul(tmp,f[i][j]));
inc(e[i+k][k],mul(tmp,add(f[i][j],e[i][j])));
}
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=i;j++) if(f[i][j]){
inc(ans,mul(dec(1,pw[j]),add(f[i][j],e[i][j])));
inc(ans,mul(mul(p2[n-i][j],f[i][j]),INF%mod));
}
cout<<mul(mul(ans,n-1),ksm(10,6*n*n));
return 0;
}

T3:洛谷画画加强版，要求联通
联通就容斥一步就好了

Code：

#include<bits/stdc++.h>
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
int mod;
inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Dec(int &x,int y){x-=y;if(x<0) x+=mod;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
inline int ksm(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a);return res;}
const int N=105;
inline int Gcd(int a,int b){return b==0?a:Gcd(b,a%b);}
int n,ans;
int fac[N],ifac[N],inv[N],gcd[N][N];
inline void init_fac(){
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=mul(ifac[i+1],i+1);
inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=mul(inv[mod%i],(mod-mod/i));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) gcd[i][j]=Gcd(i,j);
}
vector<int>dv;
int cnt[N],fa[N],val[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline void calc(){
int coef=1,tot=0;
for(int i=1;i<=n;i++) Mul(coef,ifac[cnt[i]]);
for(int &x:dv) Mul(coef,inv[x]);
int siz=dv.size();
for(int i=0;i<siz;i++) fa[i]=i,val[i]=0;
for(int i=0;i<siz;i++){
int x=dv[i];
if(x&1) tot+=(x-1)/2;
else tot+=x/2-1,val[i]=1;
}
for(int i=0;i<siz;i++)
for(int j=i+1;j<siz;j++){
int g=gcd[dv[i]][dv[j]];
int x=(dv[j]/g)&1,y=(dv[i]/g)&1;
if(x+y==2){
int f1=get(i),f2=get(j);
fa[f1]=f2;tot+=g;
}
else if(x+y==0) tot+=g;
else if(x==1) val[i]+=g;
else val[j]+=g;
}
for(int i=0;i<siz;i++) if(get(i)!=i) val[get(i)]+=val[i];
for(int i=0;i<siz;i++) if(get(i)==i) tot+=val[i]?val[i]-1:0,tot++;
inc(ans,mul(coef,ksm(2,tot)));
}
inline int C(int n,int m){
if(n<m) return 0;
int res=ifac[m];
for(int i=0;i<m;i++)
Mul(res,n-i);
return res;
}
void dfs(int v,int mx){
if(!v) return calc();
if(v<mx)return;
for(int i=mx;i<=v;i++){
cnt[i]++,dv.pb(i);
dfs(v-i,i);
cnt[i]--,dv.pop_back();
}
}
int f[N],g[N],s[N];
int main(){
n=read(),mod=read();
init_fac();
for(int i=1;i<=n;i++){ans=0;dfs(i,1);f[i]=ans-1;}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++) Dec(f[i],f[j]);
g[0]=1;ans=0;
for(int i=1;i<=n;i++){
s[i]=dec(f[i],g[i]);inc(ans,s[i]);
for(int j=n;j;j--)
for(int k=1;k*i<=j;k++) inc(g[j],mul(g[j-i*k],C(add(s[i],k-1),k)));
}
cout<<ans;
return 0;
}

最后

以上就是甜美哈密瓜为你收集整理的191009NOI模拟题解的全部内容，希望文章能够帮你解决191009NOI模拟题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。