比赛链接：https://codeforces.com/contest/908。
D. New Year and Arbitrary Arrangement
期望$dp$一般考虑从当前状态到终点状态的期望，不然有可能会出问题。
所以设$f_{i,j}$表示当前有$i$个$a$，$j$个$ab$，把剩下的东西补齐最后的$ab$个数的期望。
边界就是$f_{i,j}=j~(j\geqslant k)$。
还有就是当$i\geqslant k$的时候，用无穷级数算一下期望放多少个$a$之后会放一个$b$。
注意到一开始可以无限的放$b$，但是对答案不造成影响，所以就硬点第一个是$a$，答案就是$f_{1,0}$。
转移用记忆化搜索实现即可。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int pa,pb,k,r[1002][1002];
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
return res;
}
int f(int a,int b) {
if(b>=k) return b;
if(a>=k) return (a+b+1ll*pa*qpow(pb,mod-2)%mod)%mod;
if(r[a][b]) return r[a][b];
return r[a][b]=(1ll*pa*f(a+1,b)+1ll*pb*f(a,b+a)%mod)%mod;
}
int main() {
read(k),read(pa),read(pb);int t=qpow(pa+pb,mod-2);
pa=1ll*pa*t%mod,pb=1ll*pb*t%mod;
write(f(1,0));
return 0;
}
|
E. New Year and Entity Enumeration
好神仙啊。。
考虑对于一个集合$s$，如果他要变成好的，要生成一些什么样的数。
对于第$i$位，设$f_i$表示能被生成的数中包含第$i$位的数中包含$1$的个数最小的那个是什么。
注意到因为有取反操作，所以每一个$f_i$都是有值的。
现在有一个结论是说，对于$i,j$，如果$f_i\ne f_j$，那么$f_i\&f_j=0$.
考虑反证，假设不等于$0$，首先显然$f_j$第$i$位不可能是$1$，否则$f_i\&f_j$一定比$f_i$更优，这一来就会更新$f_i$。
如果$f_j$的第$i$位为$0$，$f_i\&(\text{~}f_j)$就会更新$f_i$。
那么可以发现这个集合里的所有数都只有可能是若干个$f_i$或起来的，就是说这些个$f_i$是最小的单元。
那么现在回到题目，首先把$T$的$f_i$求出来，考虑我们可以通过引入一些数来任意的分割任意一个$f_i$，使其变成若干个更小的单元。
那么答案就是一堆贝尔数相乘，也就是说把$n$个元素分成任意堆的方案数。
贝尔数有个递推公式，不过我懒的想那个东西了，也可以不用那个公式直接把一堆的第二类斯特林数加起来。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
char ss[52][maxn];
int cnt[maxn],fa[maxn],n,m,s[maxn][maxn],b[maxn];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void link(int x,int y) {
x=find(x),y=find(y);
if(x!=y) fa[x]=y,cnt[y]+=cnt[x];
}
int main() {
read(n),read(m);
for(int i=1;i<=m;i++) scanf("%s",ss[i]+1);
for(int i=1;i<=n;i++) fa[i]=i,cnt[i]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) {
int bo=1;
for(int k=1;k<=m;k++) if(ss[k][i]!=ss[k][j]) bo=0;
if(bo) link(i,j);
}
s[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
s[i][j]=(1ll*j*s[i-1][j]%mod+s[i-1][j-1])%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
b[i]=(b[i]+s[i][j])%mod;
int ans=1;
for(int i=1;i<=n;i++) if(fa[i]==i) ans=1ll*ans*b[cnt[i]]%mod;
write(ans);
return 0;
}
|
F. New Year and Rainbow Roads
普及组贪心题。
考虑每个绿色的作为关键点，两个绿色点之间有两种连法：
- 绿蓝绿连成一条链，绿红绿一条链。
- 绿色相连，那么上面的两条链就可以分别断掉一条边。
特判下两头的非绿色点就好了。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int n,d[maxn],p[maxn],top;
char c[maxn];
signed main() {
read(n);
for(int i=1;i<=n;i++) {
read(d[i]),scanf("%c",&c[i]);
if(c[i]=='G') p[++top]=i;
}
if(!top) {
int a=0,b=0,cc=0,dd=0;
for(int i=1;i<=n;i++)
if(c[i]=='B') cc=d[i],a=a?a:d[i];
else dd=d[i],b=b?b:d[i];
write(dd-b+cc-a);return 0;
}
int ans=0;
for(int i=2;i<=top;i++) {
int l=p[i-1]+1,r=p[i]-1,pre=p[i-1],t=0,tt=0,pp=p[i-1];
for(int j=l;j<=r;j++)
if(c[j]=='R') t=max(t,d[j]-d[pre]),pre=j;
else tt=max(tt,d[j]-d[pp]),pp=j;
t=max(t,d[p[i]]-d[pre]),tt=max(tt,d[p[i]]-d[pp]);
ans+=min(2*(d[p[i]]-d[p[i-1]]),3*(d[p[i]]-d[p[i-1]])-t-tt);
}
int p1=p[1],p2=p[1];
for(int i=p[1]-1;i;i--)
if(c[i]=='R') ans+=d[p1]-d[i],p1=i;
else ans+=d[p2]-d[i],p2=i;
p1=p[top],p2=p[top];
for(int i=p[top];i<=n;i++)
if(c[i]=='R') ans+=d[i]-d[p1],p1=i;
else ans+=d[i]-d[p2],p2=i;
write(ans);
return 0;
}
|
G. New Year and Original Order
观察下可以发现，对于一个排好序的数，我们对数位差分一下可以发现这个数是由九个形如$1111\cdots111$的数加起来得到的。
更具体的说，对于$x~(1\leqslant x\leqslant 9)$，如果有$k$个大于等于它的数位，那么他就贡献了一个$k$个$1$的数字。
那么直接数位$dp$，$f_{i,j,k,0/1}$表示当前$dp$了前$i$位，有$j$个大于等于$k$的数位，有没有贴紧上界的方案数。
转移很简单，暴力就好了。
感觉难度好不均匀啊，为啥第五题那么难，后面的简单些啊
果然是我太菜了吗
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 700+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int f[maxn][maxn][10][2],n;
char s[maxn];
void add(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int main() {
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;i++) s[i]-='0';
for(int i=1;i<=9;i++) f[0][0][i][1]=1;
for(int k=1;k<=9;k++)
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++) {
if(j||s[i]<k) add(f[i][j][k][1],f[i-1][j-(s[i]>=k)][k][1]);
add(f[i][j][k][0],1ll*f[i-1][j][k][0]*k%mod);
if(j) add(f[i][j][k][0],1ll*f[i-1][j-1][k][0]*(10-k)%mod);
add(f[i][j][k][0],1ll*f[i-1][j][k][1]*min(k,(int)s[i])%mod);
if(j) add(f[i][j][k][0],1ll*f[i-1][j-1][k][1]*max(s[i]-k,0)%mod);
}
int ans=0;
for(int k=1;k<=9;k++) {
int r=0;
for(int i=1;i<=n;i++) {
r=(1ll*r*10+1)%mod;
ans=(ans+1ll*r*(f[n][i][k][0]+f[n][i][k][1])%mod)%mod;
}
}write(ans);
return 0;
}
|
H. New Year and Boolean Bridges
这个图显然是弱联通的。
容易发现$\rm AND$表示这两个点强连通，那么可以先缩一波点，对于每个$size\geqslant 2$的强连通块，最少需要$size$条边把他们连成一个环。
剩下的连成一条链就可以满足条件了。
考虑怎么减少边数，显然如果我们把两个强连通块合并，就会少一条链的边，因为强连通块要求$size\geqslant 2$，所以一共只有$n/2$个，可以状压。
设$f_s$表示$s$这些点可不可以弄成一个强连通块，这是因为$\rm XOR$关系不能在一个强连通块中。
设$g_{k,s}$表示用$k$条链边能不能把$s$这些点连起来。
那么$g_{k,s}=\sum_{t\subset s} g_{k-1,t}f_{s-t}$。
显然这可以看做是一个或卷积，因为$s-t$和$t$实际上如果重合了答案也不会错。
所以每次拿$g$卷上$f$，直到$g_{all-1}$不为$0$就得到了最优解。
那么使用$\rm fwt$优化即可，复杂度$O(n^22^{n/2})$。
复杂度还是有点高，考虑如何优化，注意到不需要每次都$\rm fwt$，因为$\rm fwt$操作其实是子集和，所以我们可以每次利用子集容斥把$g_{all-1}$一项搞出来，那么只需要$\rm fwt$一次即可。
复杂度$O(n\cdot 2^{n/2})$。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 50+10;
const int maxm = (1<<23)+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
char s[maxn][maxn];
int n,fa[maxn],sz[maxn],id[maxn],m;
int f[maxm],g[maxm],a[maxm];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void get(int a,int b) {
a=find(a),b=find(b);
if(a!=b) fa[a]=b,sz[b]+=sz[a];
}
void fwt(int *r) {
for(int i=1;i<1<<m;i<<=1)
for(int j=0;j<1<<m;j+=i<<1)
for(int k=0;k<i;k++) r[i+j+k]+=r[j+k];
}
int main() {
read(n);for(int i=1;i<=n;i++) scanf("%s",s[i]+1),fa[i]=i,sz[i]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(s[i][j]=='A') get(i,j);
for(int i=1,v;i<=n;i++) if((v=find(i))==i) if(sz[v]>=2) id[v]=++m;
if(!m) return write(n-1),0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(s[i][j]=='X') {
int u=find(i),v=find(j);
if(u==v) return puts("-1"),0;
if(!id[u]||!id[v]) continue;
f[(1<<(id[u]-1))|(1<<(id[v]-1))]=1;
}
fwt(f);
for(int i=0;i<1<<m;i++) f[i]=!f[i];
fwt(f);
for(int i=0;i<1<<m;i++) g[i]=f[i],a[i]=1;
for(int x=0;;x++) {
int t=0;
for(int i=0;i<1<<m;i++) t+=(__builtin_popcount((1<<m)-1-i)&1?1:-1)*g[i];
if(t) return write(n+x),0;
for(int i=0;i<1<<m;i++) g[i]=g[i]*f[i];
}
return 0;
}
|