T1:
给你一个长为n的数组,下标从0开始,每个数都是0…9,你需要回答Q个询问:给出li,ri,求区间[li,ri]中所有数的乘积模10的结果。
小A轻松地解决了这道题,现在她想知道:给出n,Q,li,ri,以及每组询问的答案ansi,求原数组有多少种不同的情况?
n
,
q
≤
100
n,qle100
n,q≤100
先用中国剩余定理转化为%2和%5的情况,然后分别统计,最后乘起来
考虑一个点为0的情况,则跨过这个点的区间的答案必须全是0,可以区间DP统计一下
然后其他的情况就用带权并查集统计即可
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100#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条边。每条边有
p
1
0
6
frac{p}{10^6}
106p的概率存在,
1
−
p
1
0
6
1-frac{p}{10^6}
1−106p的概率不存在。
现在等概率在n个点中随机一个,求1号点到它的最短距离(经过的边数)。如果1号点和它不连通,则认为答案是
1
0
9
10^9
109。
求期望答案。
n
≤
400
nle400
n≤400
这种题一般就是按最短路分层,考虑层与层之间的dp
设f[i][j][k]表示第i层,用了j个点,最后一层有k个点的情况,转移枚举下一层的点数l即可做到
n
4
n^4
n4
考虑优化,发现第i层这个限制不必要,可以去掉,但是我们需要一个新的状态表示i这一层。即到达某个状态时距离的期望值
那么我们设两个数组f,e分别表示概率和期望,转移就考虑这一层的点和下一层的点的连通性,下一层的点必须都和这一层中至少一个点连边,且不属于下一层的点不能与这一层连边,再乘个组合数表示选点的方案数,那概率就可以直接转移了
考虑期望的转移,设这一层的点到1号点的距离为dis,则下一层就是dis+1,那么期望就是
f
[
i
]
[
j
]
∗
(
d
i
s
+
1
)
=
f
[
i
]
[
j
]
∗
∗
d
i
s
+
f
[
i
]
[
j
]
=
e
[
i
]
[
j
]
+
f
[
i
]
[
j
]
f[i][j]*(dis+1)=f[i][j]**dis+f[i][j]=e[i][j]+f[i][j]
f[i][j]∗(dis+1)=f[i][j]∗∗dis+f[i][j]=e[i][j]+f[i][j]
也可以用期望的线性性证明
因为除了1号点,每个点是等价的,所以我们算一个点的期望,最后乘个n-1即可
算一个点的期望就枚举所有状态,然后考虑在当前状态下这个点连不连最后一层的某一个点,统计一下即可
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99#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模拟题解内容请搜索靠谱客的其他文章。
发表评论 取消回复