五一省选集训Day1

A

先搞个多项式 (P(x)) ，次数为 (i) 的系数表示随机一次给 (z) 加上 (i) 的概率（也就是输入）。如果你求出来 (Q=P^n)，答案显然是 (sum_{i=0}^{x-1}iQ[i]+x(1-sum_{i=0}^{x-1}Q[i]))

40pts

考场上写的做法 (O(xlog xlog n))

只需要写个 NTT 直接倍增求多项式快速幂就好了

60pts

[egin{aligned} Q=P^n \ ln Q = nln P\Q=e^{n ln P} end{aligned} ]

板子拉一拉就好了。(O(xlog x))

注意做多项式 exp 的前提是要没有常数项也就是这个多项式的常数项要求是 1。这个题目保证了有常数项如果没有的话我们就可以通过除掉一个单项式来让最低位是常数项最后加回去即可，

100pts

好像是个新科技（或套路）

我们考虑 (P^{n+1}) 的两种求导方法，并加以推导：

[egin{aligned} (P^{n+1})' = (n+1)P^{n}P'\(P^{n+1})' = (P*P^n)' = P(P^{n})'+P'P^n\(n+1)P^nP'=P(P^{n})'+P'P^n \ nP^nP'=P(P^{n})'\nQP'=PQ' end{aligned} ]

考虑我们拿出多项式的第 (n) 项

[egin{aligned} nsum_{i=1}^k iP[i]Q[n-i+1] = sum_{i=0}^k (n-i+1)P[i]Q[n-i+1]\Q[n+1]=frac{nsum_{i=1}^k iP[i]Q[n-i+1]-sum_{i=1}^k (n-i+1)P[i]Q[n-i+1]}{(n+1)P[0]} end{aligned} ]

代入计算即可。时间复杂度 (O(xk))

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e7 + 5;
const int ha = 998244353;
int n,k,x;
int P[MAXN],Q[MAXN];

inline int qpow(int a,int n=ha-2){
	int res = 1;
	while(n){
		if(n & 1) res = 1ll*res*a%ha;
		a = 1ll*a*a%ha;
		n >>= 1;
	}
	return res;
}

int main(){
	scanf("%d%d%d",&n,&k,&x);
	int sm = 0;
	FOR(i,0,k) scanf("%d",P+i),sm += P[i];
	sm = qpow(sm);
	FOR(i,0,k) P[i] = 1ll*P[i]*sm%ha;
	Q[0] = qpow(P[0],n);int inv=qpow(P[0]);
	int ans = 0;sm = Q[0];
	FOR(i,1,x-1){
		FOR(j,1,std::min(i,k)){
			(Q[i] += 1ll*j*P[j]%ha*Q[i-j]%ha) %= ha;
		}
		Q[i] = 1ll*Q[i]*n%ha;
		FOR(j,1,std::min(i,k)) (Q[i] += ha-1ll*(i-j)*P[j]%ha*Q[i-j]%ha) %= ha;
		Q[i] = 1ll*Q[i]*inv%ha*qpow(i)%ha;
		(ans += 1ll*i*Q[i]%ha) %= ha;
		(sm += Q[i]) %= ha;
	}
	(ans += 1ll*x*(ha+1-sm)%ha) %= ha;
	printf("%d
",ans);
	return 0;
}

B

60pts做法

考场做法

我们先考虑最后一段连续的都是1的情况

设最后一个 (0) 的位置是(p) ，这个字符串被随机出的概率显然是 (2^{-p})

于是我们去枚举这个 (p)，考虑计算出方案数乘一下概率就好。

枚举这些钦定的位置是全 0 还是全 1 ，分类讨论一下:

全 0：显然 (p) 后面不能存在钦定的位置然后组合数选一下再按照 (p) 位置是否被钦定组合数一下（如果没被钦定这个位置不能被涂1 要减去）

全 1：首先 (p) 这个位置不能被钦定，然后记录一下 (p) 前面有多少个钦定了的位置剩下的位置组合数算一下选出0 的位置即可。

另一种情况翻转过来就可以所以答案要乘 (2)

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

const int MAXN = 2e5 + 5;
const int ha = 998244353; 
int a[MAXN];
int n,q;

int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
	int res = 1;
	while(n){
		if(n & 1) res = 1ll*res*a%ha;
		a = 1ll*a*a%ha;
		n >>= 1;
	}
	return res;
}

inline void prework(){
	fac[0] = 1;
	FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
	inv[MAXN-1] = qpow(fac[MAXN-1]);
	ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
	if(n < m) return 0;
	if(!m) return 1;
	return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}
int sm[MAXN];
const int inv2=(ha+1)/2;
int pw[MAXN];
int main(){
	prework();
	read(n);read(q);int all = 0;
	pw[0] = 1;FOR(i,1,MAXN-1) pw[i] = 1ll*pw[i-1]*inv2%ha;
	while(q--){
		int k;read(k);int mx = 0;
		FOR(i,1,k) read(a[i]),mx = std::max(mx,a[i]);
		FOR(i,1,2*n) sm[i] = 0;FOR(i,1,k) sm[a[i]] = 1;
		FOR(i,1,2*n) sm[i] += sm[i-1];
		int ans = 0;
		FOR(i,n,2*n-1){//最后一个 0
			int t0=n,t1=i-n;
			if(mx <= i){
				(ans += 1ll*pw[i]*C(i-k-(sm[i]-sm[i-1]==0),t1)%ha)%=ha;
			}
			if(sm[i]-sm[i-1] == 0) (ans += 1ll*pw[i]*C(i-1-sm[i],n-1)%ha) %= ha;
		}
		ans = 1ll*ans*2%ha;
		printf("%d
",ans);
	}
	return 0;
}

100pts做法

大家肯定都会去想搞个前缀和快速维护但是我考场上以为要对于每个 (k) 维护就自闭了。

我们注意到 本质不同的 (k) 的种类数只会有 (O(sqrt {sum k})) 个。

证明考虑等差数列求和即可。

于是我们现在枚举 (k) 把询问放在一起处理，下面我们来对着上面的代码优化：

if(mx <= i){
	(ans += 1ll*pw[i]*C(i-k-(sm[i]-sm[i-1]==0),t1)%ha)%=ha;
}

如果这一位没有被钦定就是 (pw[i]inom {i-k-1}{i-n}) 否则是 (pw[i]inom {i-k}{i-n})

我们去枚举计算被钦定的位没背钦定的一定被分成若干段预处理 (pw[i]inom{i-k-1}{i-n}) 的前缀和即可。注意一下边界 x1

if(sm[i]-sm[i-1] == 0) (ans += 1ll*pw[i]*C(i-1-sm[i],n-1)%ha) %= ha;

这个有点难。。我想了一会。

我们还是去找出中间那些段，然后我们发现每段内一定是形如 (pw[i]*inom{i-1-c}{n-1}) 的形式 (c) 是和前面有多少个被钦定的位置的数量。那么我们预处理出来 (pw[i]*inom {i-1}{n-1}) 的前缀和，发现一段一定会整体少乘 (pw[c]) 乘上去就好了。注意边界 x2

发现上面的所有操作都是和 (k) 有关的所以复杂度是很正确的 (O(nsqrt n))（(n,k,q)同阶）

C

好像你需要猜结论：在如此小的数据范围内每个组最多只会有两个集合。

如果是奇数的 subtask 的话直接把大小为 (i) 和大小为 (k-i) 的连边搞个二分图屁屁额就好了。

于是跑一个一般图最大匹配但是我不会带花树所以咕咕咕了。反正也不太会。。