斗主地[NOI2019]

发表于 分类于

链接

loj

题解

考虑一次洗牌操作的意义：

这样的洗牌是均匀的，因此每种合法方案的概率一样。

观察样例可以发现，最终每个位置答案的期望是 $\frac{7}{4},\frac{9}{4},\frac{11}{4},\frac{13}{4}$。这是一个一次函数！

于是经过打表验证，设最后第 $i$ 个位置的答案为 $F(i)$，则 $F$ 是一个不超过二次的函数！

打表程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
srand(20030403);
n=read(); m=read();
fo(i,1,n) a[i]=i;
fo(i,1,m) b[i]=read();
int T=10000000;
fo(ti,1,T)
{
	fo(i,1,n) c[i]=a[i],id[i]=i;
	fo(j,1,m)
	{
		random_shuffle(id+1,id+n+1);
		sort(id+1,id+b[j]+1);
		sort(id+b[j]+1,id+n+1);
		fo(i,1,n) d[id[i]]=c[i];
		fo(i,1,n) c[i]=d[i];
	}
	fo(i,1,n) ans[i]+=c[i];
}
fo(i,1,n) printf("%.3lf ",(db)ans[i]/T);

那么只需要记住 $F(1),F(2),F(3)$ 即可。

那么对于每次洗牌，设第一堆有 $x$ 张牌，拉格朗日插值一下算出 $F(x+1),F(x+2),F(x+3)$，然后用组合数学推超级多种情况以后算出新的 $F(1),F(2),F(3)$ 就好了。

时间复杂度 $O(m+q)$。

程序

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;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
ll mod=998244353,inv2,invn,invn2,invn3;
inline ll Pow(ll x,int y)
{
	ll ans=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) ans=ans*x%mod;
	return ans;
}
ll E1,E2,E3,F1,F2,F3,G1,G2,G3;
inline ll F(ll x)
{
	if(x==1) return E1;
	else if(x==2) return E2;
	else if(x==3) return E3;
	return (E1*(x-2)%mod*(x-3)%mod*inv2-E2*(x-1)%mod*(x-3)%mod+E3*(x-1)%mod*(x-2)%mod*inv2+mod)%mod;
}
int n,m,opt;
int main()
{
	FO(landlords);
	n=read(); m=read(); opt=read();
	inv2=(mod+1)/2; invn=Pow(n,mod-2); invn2=Pow(1ll*n*(n-1)%mod,mod-2); invn3=Pow(1ll*n*(n-1)%mod*(n-2)%mod,mod-2);
	E1=Pow(1,opt),E2=Pow(2,opt),E3=Pow(3,opt);
	ll x;
	fo(i,1,m)
	{
		x=read();
		F1=F(x+1); F2=F(x+2); F3=F(x+3);
		G1=E1; G2=E2; G3=E3;
		E1=(G1*x+F1*(n-x))%mod*invn%mod;
		E2=(G2*x%mod*(x-1)%mod+(G1+F1)*x%mod*(n-x)%mod+F2*(n-x)%mod*(n-x-1)%mod)%mod*invn2%mod;
		E3=(G3*x%mod*(x-1)%mod*(x-2)+(F1+G2+G2)%mod*x%mod*(n-x)%mod*(x-1)+(G1+F2+F2)%mod*x%mod*(n-x)%mod*(n-x-1)+F3*(n-x)%mod*(n-x-1)%mod*(n-x-2))%mod*invn3%mod;
	}
	CASET printf("%lld\n",F(read()));
	return 0;
}