homo’s weekly contest
前置知识:容斥原理
卡住了杨同学捏。
考虑一个比较简单的情况,只有报名了两个周赛,分别是2和3周一次,一共10周。则要比赛的周是2,3,4,6,8,9,10。而2,4,6,8,10是2的倍数,3,6,9是3的倍数,如果简单的相加,那么6被计算了两次,需要减去。这便是容斥原理。不明白的建议先补这个前置知识。这题是容斥原理的模板题。
我们通过二进制枚举的方式枚举20场比赛里的所有情况。出现奇数次的要加上,偶数次的要减去,如果最小公倍数已经大于最大周那么break即可,不会对答案产生贡献。
#include <iostream>
#define ll long long
using namespace std;
const int N = 25;
ll a[N];
ll n, m;
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
m /= 7; //天转周
for(int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for(int i = 1; i < 1 << n; i++)
{
ll temp = 1, op = -1, lcm = 0;
for(int j = 0; j < n; j++)
{
if(i >> j & 1)
{
op = -op;
if(!lcm) lcm = a[j];
else lcm = lcm / gcd(lcm, a[j]) * a[j];
if(lcm > m)
{
lcm = -1;
break;
}
}
}
if(~lcm) ans += op * (m / lcm);
}
cout << ans;
return 0;
}
前置知识:快速幂
根据小学数学知识,所有的分发方案有$m^n$种(每个座位有$m$种选择),则不会发生作弊事件的方案数是$m*(m-1)^{n-1}$(第一个座位$m$种选择,剩下$n-1$个座位,每个都有$m-1$种选择,因为要与前一个不同)那么发生作弊事件的方案数就是两者相减。注意对负数取模结果仍为负数。
#include <iostream>
#define ll long long
using namespace std;
const int mod = 114514;
int qmi(ll a, ll p)
{
ll res = 1;
while(p)
{
if(p & 1) res = res * a % mod;
a = a * a % mod;
p >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("data.in","r",stdin);
int t;
cin >> t;
while(t--)
{
ll n, m;
cin >> n >> m;
ll res = qmi(m, n), fine = (m * qmi(m - 1, n - 1)) % mod;
ll cheated = ((res - fine) % mod + mod) % mod;
cout << cheated << " " << fine << endl;
}
return 0;
}
来搞mc开发~