脚本宝典收集整理的这篇文章主要介绍了2022/1/2，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

2022/1/2

[ D. shuffle ]( PRoblem - D - Codeforces (Unofficial mirror sITe, accelerated for Chinese users) )

思路

遍历字符串

考虑一个包含k+2个1的字符串，去掉第一个1及其前面部分，和最后一个1后面部分。这个字符串就变成了包含k个1的字符串。

那么这个字符串的排列组合数是(C_{len}^{k})。

接着遍历到下一组包含k个1的字符串时，重复的部分是上一个字符串去掉第一个1及其前面部分，剩下的数重新排列组合的值，即(C_{len-x}^{k-1})。

这样一直处理下去即可

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<char, int >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi First
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=5007;
const ll mod=998244353;
ll T,n,k,f[qs],a[qs],pw[qs];

ll qpow(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&amp;1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
} 

ll cal(ll fn,ll fm){
	ll x=pw[fn];
	ll y=pw[fm]*pw[fn-fm]%mod;
	ll ret=x*qpow(y,mod-2)%mod;
	return ret;
}

int main(){
	
	pw[0]=1;
	for(int i=1;i<=5007;++i) pw[i]=i*pw[i-1]%mod;
	string s;

		n=read(),k=read();	
		cin>>s; s=" "+s;
		int cnt=0;
		for(int i=1;i<=n;++i){
			f[i]=f[i-1];
			if(s[i]=='1'){	
				a[++cnt]=i;
			}
			else f[i]+=1;
		}
		a[++cnt]=n+1;
		if(k==0||cnt-1<k){
			cout<<"1n";
			return 0;
		}
		ll sum=0,ans=0;
		for(int i=k;i<cnt;++i){
			ll p=i-k+1;
			ll len=a[i+1]-a[p-1]-1;
			ans=ans-sum+cal(len,k);
			ans=(ans+mod)%mod;
		//	cout<<"len="<<len<<"  clen="<<cal(len,k)<<"n";
			ll fl=a[p]-a[p-1];
			sum=cal(len-fl,k-1);
		//	cout<<"sum="<<sum<<"n";
		}
		cout<<ans<<"n";
	return 0;
}

[ E. Christmas Chocolates ]( Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users) )

思路

当询问两个数x,y之间的次数时，应该是大数x变小，用大于等于x的第一个2的幂次-x。这样能保证x==y的次数时最小的

这样构造出来的树是这个样子

那么这道题就变成了询问树的直径

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<char, int >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=2e5+7;
const ll mod=998244353;
ll n,a[qs];

int dis(int x,int y){
	int sum=0;
	while(x!=y){
		int i;
		for(i=0;(1<<i)<;max(x,y);++i);
		if(x>y) x=(1<<i)-x;
		else y=(1<<i)-y;
	//	cout<<"**x="<<x<<"  y="<<y<<"n";
		sum++;
	}
	return sum;
}

int get(int x){
	int Max=-1,id;
	for(int i=1;i<=n;++i){
		int d=dis(a[x],a[i]);
		//cout<<"x="<<x<<" i="<<i<<" d="<<d<<"n";
		if(d>Max){
			Max=d; id=i;
		}
	}
	return id;
}

int main(){


	n=read();
	for(int i=1;i<=n;++i) a[i]=read();

	int x=get(1);
	int y=get(x);
	cout<<x<<" "<<y<<" "<<dis(a[x],a[y])<<"n";
	
	
	
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的2022/1/2全部内容，希望文章能够帮你解决2022/1/2所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。