求助UB
  • 板块灌水区
  • 楼主alpharchmage
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/30 16:16
  • 上次更新2024/11/30 18:21:35
查看原帖
求助UB
411141
alpharchmage楼主2024/11/30 16:16

这份代码哪里有UB,们?

/*
1.能否二分答案?
2.可以倒着思考问题?
3.打一个小表
4.寻找结论
5.是DP & 记忆化搜索吗?
6.是否有单调性?
7.注意取模(数字写没写错 , 是否取了模)
8.能否tarjan缩个点?
9.用一下莫队?
*/
#include<bits/stdc++.h>
#define int long long
#define mod (int)(1e9 + 7)
using namespace std;
int T = 0;
array<int , 200100> fact , fact_inv;
int quick_pow(int x , int y)
{
	int res = 1;
	while(y)
	{
		if(y & 1)
		{
			res *= x;
			res %= mod;
		}
		x *= x;
		x %= mod;
		y /= 2;
	}
	return res;
}
int get_inv(int x)
{
	return quick_pow(x , mod - 2);
}
int C(int n , int m)
{
	return fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	fact[0] = 1;
	for(int i = 1;i <= 2e5;++ i) fact[i] = fact[i - 1] * i % mod;
	for(int i = 0;i <= 2e5;++ i) fact_inv[i] = get_inv(fact[i]);
	cin >> T;
	while(T --)
	{
		int n = 0 , k = 0 , one = 0 , ans = 0;
		cin >> n >> k;
		for(int i = 1;i <= n;++ i)
		{
			int tmp = 0;
			cin >> tmp;
			one += tmp;
		}
		for(int i = k / 2 + 1;i <= min(one , k);++ i)
		{
			ans += (C(one , i) * C(n - one , k - i) % mod);
			ans %= mod;
		}
		cout << ans << '\n';
	}
	cout << endl;
	return 0; 
}
2024/11/30 16:16
加载中...