NOI2019 斗主地

link

题解

发现随机归并后每种可能的状态概率是一样的。

把操作反着看,发现相当于每次等概率随机一些牌放到最前面。

对于type=1,答案相当于第i张卡做完第m..1次随机,在它前面的卡数期望+1,相当于每张卡经过m次随机在它前面的概率和+1

于是我们可以只考虑一张卡在它前面或者在它后面。

那么f[x][0/1]表示顺序做完第m..x次随机,某张卡在它前面/后面,最后在它前面的概率。

对于type=1,答案相当于在它前面的(卡数平方+2卡数)期望+1,也就相当于$2\times$每对卡(无先后顺序)经过m次随机都在它前面的概率和+$3\times$ 每张卡经过m次随机在它前面的概率和+1

再记g[x][0/1/2]表示顺序做完第m..x次随机,某对卡都在它前面/一张在前一张在后/都在它后面,最后都在它前面的概率。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/*
Author: QAQ Automaton
Lang: C++
Prog: landlords.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define inf 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline bool read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}

inline bool read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}
inline bool read (char &x) {
x=gc();
return x!=EOF;
}
inline bool read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r')if(*x==EOF)return 0;
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
return 1;
}
template<typename A,typename ...B>
inline bool read(A &x,B &...y){
return read(x)&&read(y...);
}
// print a signed integer
inline bool write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}

inline bool write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}
inline bool write (char x) {
putc(x);
return 0;
}
inline bool write(const char *x){
while(*x){putc(*x);++x;}
return 0;
}
inline bool write(char *x){
while(*x){putc(*x);++x;}
return 0;
}
template<typename A,typename ...B>
inline bool write(A x,B ...y){
return write(x)||write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[105],b[105];
int fac[10000005],inv[10000005],invf[10000005]; const int p=998244353;
int down(int a,int b){return b<0||a<b?0:fac[a]*invf[a-b]%p;}
int C(int a,int b){return b<0||a<b?0:fac[a]*invf[a-b]%p*invf[b]%p;}
int fpm(int a,int b){
int c=1;
for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
int n,m,type;
int f[500005][2],g[500005][3];
signed main(){
freopen("landlords.in","r",stdin);
freopen("landlords.out","w",stdout);
read(n,m,type);
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=inv[i]*invf[i-1]%p;
}
if(type==1){
f[0][0]=1;
f[0][1]=0;
for(int i=1;i<=m;++i){
int x;
read(x);
int w=C(n-2,x-1)*fpm(C(n,x),p-2)%p;
f[i][0]=(f[i-1][0]*(p+1-w)+f[i-1][1]*w)%p;
f[i][1]=(f[i-1][0]*w+f[i-1][1]*(p+1-w))%p;
}
}
else{
f[0][0]=1;
f[0][1]=0;
g[0][0]=1;
g[0][1]=g[0][2]=0;
for(int i=1;i<=m;++i){
int x;
read(x);
int qaq=fpm(C(n,x),p-2);
int w=C(n-2,x-1)*qaq%p;
f[i][0]=(f[i-1][0]*(p+1-w)+f[i-1][1]*w)%p;
f[i][1]=(f[i-1][0]*w+f[i-1][1]*(p+1-w))%p;
int c0=C(n-3,x)*qaq%p,c1=C(n-3,x-1)*qaq%p,c2=C(n-3,x-2)*qaq%p,c3=C(n-3,x-3)*qaq%p;
g[i][0]=((c0+c1+c1+c2+c3)*g[i-1][0]+(c2+c2)*g[i-1][1]+(c1)*g[i-1][2])%p;
g[i][1]=((c1+c2)*g[i-1][0]+(c0+c1+c2+c3)*g[i-1][1]+(c1+c2)*g[i-1][2])%p;
g[i][2]=((c2)*g[i-1][0]+(c1+c1)*g[i-1][1]+(c0+c1+c2+c2+c3)*g[i-1][2])%p;
}
}
int q;
read(q);
for(;q;--q){
int x;
read(x);
if(type==1)write(((x-1)*f[m][0]+(n-x)*f[m][1]+1)%p,'\n');
else{
write((1+3*f[m][0]*(x-1)+3*f[m][1]*(n-x)+(x-1)*(x-2)%p*g[m][0]+2*(x-1)*(n-x)%p*g[m][1]+(n-x)*(n-x-1)%p*g[m][2])%p,'\n');
}
}
return 0;
}
# dp

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×