0905 模拟赛

T1

题意

题目链接
求(1-n)中多少个长为(m)的序列(a)满足：
1.(a_1=1,a_m=n)
2.(forall i,a_{i+1}ge k)
求方案数的奇偶性，数据有(T) 组，满足：
(n,m,q leq 10^9, Tleq 2*10^6)

Idea

1.考虑(k=1) 方案数为(inom{n-2}{m-2})
2.考虑(k ot =1)，即(k ge 1)
由题意得：令所选的集合为(b_i),则对于集合里的每个数有(b_{i+1}-b_i ge k),
那么在原集合(a_i)中不能选的数字有((m-1) imes (k-1))个, 且开头结尾不能选，那么方案数为
(inom{n-(m-1)ast (k-1)-2}{m-2})
由(Lucas)定理得(inom{n}{m} mod p=inom{n mod p}{m mod p}ast inom{n/p}{m/p} mod p)
令(p=2:inom {n mod 2}{m mod 2})只有四种取值，且仅当((n mod 2)ge (m mod 2))
又因(mod 2) 相当于取出该数字在二进制下的最后一位，若满足(n)的每一位都(ge m) 的每一位
就要满足(n~and~m=m)

Code

int n,m,k;
signed main(){ 
	int T=read();
	while(T--){
		n=read(); m=read(); k=read();
		int x=n-(m-1)*(k-1)-2;
		int y=m-2;
		if((x&y)==y) puts("Yes");
		else puts("No");
	}
	return 0;
}

T2

题目链接

T3

题意：

题目链接
随机生成一个 (m + 1) 个数的数列，第一个数为 0, 生成第 (i)个数时，在前 (i−1) 个数中等概率选择一个数 (k), 则第 (i) 个数为(k + 1)。每个数均有一个对应的权值，求数列权值和的期望。

(S)：数列的权值和

(X_i)：第i个数的权值（(X_1)为定值0，所以忽略不计）

[S=sum_{i=2}^{m+1}X_i ]

根据期望的线性性有

[E(S)=sum_{i=2}^{m+1}E(X_i) ]

只要求出(E(X_i))就可以了

(P_i(j))：序列的第i个数为j的概率

[E(X_i)=sum_{j=1}^{i-1}P_i(j)ast a_j ]

现在只要求出(P_i(j))就可以了

(j)的出现要求在前(i-1)个数中随机到(j-1)

[P_i(j)=sum_{k=1}^{i-1}frac {1}{i-1}P_k(j-1) ]

综上所述

[E(S)=sum_{i=2}^{m+1}sum_{j=1}^{i-1}a_j sum_{k=1}^{i-1}P_k(j-1) ]

Code（这份和题解相符）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<queue>
#define int long long
#define maxn 100001
#define inf 2147483647
#define mod 998244353
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std; 
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int a[maxn],y[25];
int x[25];//第i次玩的期望战斗次数 
int p[25][25];//第i次玩的是章节j的概率  
inline int power(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
signed main(){	
	freopen("kiseki.in","r",stdin);
	freopen("kiseki.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m+1;i++) y[i]=power(i,mod-2);//逆元 
	x[1]=0; p[1][0]=1;//序章 
	for(int i=2;i<=m+1;i++)//第i次 
	for(int j=1;j<i;j++){//玩的章节 
		for(int k=1;k<i;k++)//枚举存档 
			p[i][j]=(p[i][j]+p[k][j-1]*y[i-1]%mod)%mod;
		x[i]=(x[i]+p[i][j]*a[j]%mod)%mod;
	}
	int ans=0;
	for(int i=2;i<=m+1;i++) ans=(ans+x[i])%mod;
	cout<<ans; 
    return 0;
}