D. Santa‘s Bot (概率、逆元)

系统管理员 2021-07-16 14:55 298阅读 0赞

[题目][Link 1]

首先每个礼物被抽到的概率不是均等的，是先从n个人里等概率选出一个人，再从k个礼物等概率选出一个礼物，第1个人每个礼物选中概率1/(n*k1) 第二人 1/(n*k2)。对于一个礼物c产生的贡献= (1/(n*ki))【其被选中的概率】*(num\[c\]/n)【正确给到孩子的概率】，需要先记录出每个礼物对应几个孩子，即该礼物的数量。把分母用逆元算即可。

Code:

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<iomanip>
    #include<map>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    map<ll, ll > a;
    ll Mod = 998244353;
    ll f[Max];
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    void init() { 
    	f[0] = 1;
    	for (int i = 1;i <= 1e6;i++) { 
    		f[i] = f[i - 1] * i % Mod;
    	}
    }
    ll cal(ll n, ll m) { 
    	if (n < m) return 0;
    	return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
    }
    
    ll inv(ll n) { return  qpow(n,Mod - 2); }
    
    vector<ll> lst[Max];
    
    int main()
    { 
    	ll n;cin >> n;
    	init();
    	ll sum = 0;
    	ll ans = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int m;cin >> m;
    		for (int j = 1;j <= m;j++)
    		{ 
    			int c;cin >> c;
    			lst[i].push_back(c);
    			a[c]++;
    		}
    	}
    	for (int i = 1;i <= n;i++)
    	{ 
    		ll k = lst[i].size();
    		for (ll j : lst[i])
    		{ 
    			ans += a[j] * inv(n) % Mod * inv(n) % Mod * inv(k) % Mod;
    			ans %= Mod;
    		}
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/contest/1279/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，298人围观）

还没有评论，来说两句吧...

相关阅读

相关乘法逆元整理

乘法逆元 1.费马小定理 > 如果 $ a,p $ 互质，那么 $ a^\{p-1\} ≡ 1(mod p) $ > 又由逆元方程知 $ a\*x ≡ ...

约定不等于承诺〃/ 2024年04月20日 10:25/ 0 赞/ 64 阅读

相关线性求逆元

线性求逆元求1~n在%mod意义下的逆元 ![1735240-20190814082511164-1340216219.png][] mi[1]=1;

以你之姓@/ 2023年08月17日 15:35/ 0 赞/ 96 阅读

相关逆元详解求逆元的方法汇总

[基础知识][Link 1] [求乘法逆元的几种方法][Link 2] [逆元详解][Link 3] [Link 1]: http://blog.csdn.net/fe

秒速五厘米/ 2022年06月13日 05:45/ 0 赞/ 211 阅读

相关详解--乘法逆元

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。对于正整数![20140613102654328][]和![20140613

怼烎@/ 2022年06月11日 07:48/ 0 赞/ 347 阅读

相关乘法逆元 51Nod - 1256——同余定理+逆元(乘法逆元) (拓展欧几里得算法求逆元)

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \ M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数

比眉伴天荒/ 2022年05月19日 13:41/ 0 赞/ 249 阅读

相关 A/B——同余定理+逆元（除法逆元）

同余定理: 数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)

太过爱你忘了你带给我的痛/ 2022年05月19日 11:18/ 0 赞/ 273 阅读

相关求逆元基本方法

乘法逆元小结 > 乘法逆元，一般用于求 > > $\\frac\{a\}\{b\} \\pmod p$ > > 的值（$p$ 通常为质数），是解决模意义下分数数值的必要手

旧城等待，/ 2021年11月22日 08:10/ 0 赞/ 447 阅读

相关 D. Radio Towers（dp、逆元）

[题目][Link 1] 思路：状态方程dp\[i\]代表从1–n都被照亮的方法数。 dp\[i\]=dp\[i-1\]+dp\[i-3\]+dp\[i-5

清疚/ 2021年09月07日 06:10/ 0 赞/ 246 阅读

相关逆元

参考于此篇博客：[https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html][https_www.cnblogs

刺骨的言语ヽ痛彻心扉/ 2021年09月07日 06:10/ 0 赞/ 389 阅读

相关 D. Santa‘s Bot (概率、逆元)

[题目][Link 1] 首先每个礼物被抽到的概率不是均等的，是先从n个人里等概率选出一个人，再从k个礼物等概率选出一个礼物，第1个人每个礼物选中概率1/(nk1) 第二

系统管理员/ 2021年07月16日 14:55/ 0 赞/ 299 阅读