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
#define ll long long
#define pii pair
#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&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
[ E. Christmas Chocolates ]( Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users) )
思路
当询问两个数x,y之间的次数时，应该是大数x变小，用大于等于x的第一个2的幂次-x。这样能保证x==y的次数时最小的
这样构造出来的树是这个样子
那么这道题就变成了询问树的直径
参考代码
#include
#define ll long long
#define pii pair
#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<y) x=(1<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<