[ABC215G]Colorful Candies 2

2024-03-16 22:48
文章标签 colorful candies abc215g

本文主要是介绍[ABC215G]Colorful Candies 2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Colorful Candies 2

题解

首先对于一个球,它对答案产生贡献当且仅当有至少一个它这种颜色的球被选中。
我们记颜色为 i i i的球有 c i c_{i} ci个,当我们选择 j j j个时,我们可以用容斥的方法的到它被选择的概率, ( n j ) − ( n − c i j ) ( n j ) \frac{\binom{n}{j}-\binom{n-c_{i}}{j}}{\binom{n}{j}} (jn)(jn)(jnci)
很明显有,选择 j j j个球的期望颜色数为 ∑ i = 1 n ( n − c i j ) ( n j ) \frac{\sum_{i=1}^{n}\binom{n-c_{i}}{j}}{\binom{n}{j}} (jn)i=1n(jnci)
但如果直接跑的话 O ( n 2 ) O\left(n^2\right) O(n2)时会 T T T飞的,考虑优化。

很明显,对于球的个数的某种颜色,他们的贡献时相同的,我们可以记录下为球个数为 i i i的颜色的数量。
对于个数小于 ⩽ n \leqslant \sqrt{n} n 的,我们将它们统一计算,而大于 n \sqrt{n} n 的部分,我们可以单独计算,这一部分数量肯定是小于 n \sqrt{n} n 的。

时间复杂的 ( n n ) \left(n\sqrt{n}\right) (nn )

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue> 
using namespace std;
#define MAXN 50005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=1000000000000000000LL;
const int mo=998244353;
const int inv2=499122177;
const int jzm=2333;
const int n1=200;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-7;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,a[MAXN],b[MAXN],tot,sum[MAXN],d[MAXN],fac[MAXN],inv[MAXN],f[MAXN];
vector<int>vec;
void init(){fac[0]=fac[1]=inv[0]=inv[1]=f[1]=1;for(int i=2;i<=5e4;i++){fac[i]=1ll*i*fac[i-1]%mo;f[i]=1ll*(mo-mo/i)*f[mo%i]%mo;inv[i]=1ll*f[i]*inv[i-1]%mo;}
}
int C(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
int iC(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*inv[x]*fac[y]%mo*fac[x-y]%mo;
}
signed main(){read(n);init();for(int i=1;i<=n;i++)read(a[i]),b[++tot]=a[i];sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b,sum[a[i]]++;for(int i=1;i<=tot;i++)if(sum[i]<=n1)d[sum[i]]++;else vec.pb(sum[i]);for(int i=1;i<=n;i++){int ans=0;for(int j=1;j<=n1;j++)ans=add(ans,1ll*d[j]*add(C(n,i),mo-C(n-j,i),mo)%mo,mo);for(int j=0;j<vec.size();j++)ans=add(ans,add(C(n,i),mo-C(n-vec[j],i),mo),mo);ans=1ll*ans*iC(n,i)%mo;printf("%d\n",ans);}return 0;
}

谢谢!!!

这篇关于[ABC215G]Colorful Candies 2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816974

相关文章

[置顶]LCM性质 + 组合数 - HDU 5407 CRB and Candies

CRB and Candies Problem's Link  Mean:  给定一个数n,求LCM(C(n,0),C(n,1),C(n,2)...C(n,n))的值,(n<=1e6). analyse: 很有趣的一道数论题! 看了下网上别人的做法,什么Kummer定理我还真没听说过,仔细研究一下那个鬼定理真是涨姿势了! 然而这题我并不是用Kummer那货搞的(w

【HDU】5574 Colorful Tree【子树染色,询问子树颜色数——线段树+bit+lca+set】

题目链接:【HDU】5574 Colorful Tree 题目大意:对一个子树染色,询问一个子树的颜色数。 题目分析: set set维护每种颜色所在的 dfs dfs序区间,修改均摊 nlogn nlogn。 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , i

poj 2886 Who Gets the Most Candies?

单点更新,还有凡素数表,所谓反素数, 对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4. 定义:如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数. 现在给一个N,求出不超过N的最大的反素数. 比如:输入1000 输出 840 思维过程: 求[1..N]中最大的反素数-->求约数最多的数 如果求约数的个数

POJ 2886 Who Gets the Most Candies? (线段树,单点更新)

http://poj.org/problem?id=2886 Who Gets the Most Candies? Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 9426 Accepted: 2871Case Time Limit: 2000MS Description N children are sitt

Distribute Candies问题及解法

问题描述: Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribut

B. Inna and New Matrix of Candies

Inna likes sweets and a game called the "Candy Matrix". Today, she came up with the new game "Candy Matrix 2: Reload". The field for the new game is a rectangle table of size n × m. Each line of the

Codeforces 400B Inna and New Matrix of Candies(暴力)

题目链接:Codeforces 400B Inna and New Matrix of Candies 题目大意:给出n和m表示有n行m列,每一行上有一个小人G和一个糖果S,每次操作可以让所有小人一起向右移动,直到有某个小人碰到糖果或者是走到尽头,问说至少要多少次操作才可以使得所有小人都吃到糖果,如果有小人吃不到糖果输出-1. 解题思路:暴力,对于每一行记录住小人移动到糖果需要多少

LeetCode 575. Distribute Candies

575. Distribute Candies 一、问题描述 Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding

poj 3159 Candies(查分约束+堆栈优化的spfa最短路模板)

题目链接:点击打开链接 Description During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had fly

leetcode575-Distribute Candies

题目 Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可能吃到最多不同种类的糖。 给你一个长度为 n 的整数数组 candyType ,返回: Alice