K Random 简单的概率题，直接能推出公式为 \((n - m) / 2\) 但是不能就这样简单的去算，加减乘与模运算的顺序交换不会影响结果，但是除法不行。这个题目要求对一个大质数取模，原式里
简单的概率题，直接能推出公式为\((n - m) / 2\)
但是不能就这样简单的去算，加减乘与模运算的顺序交换不会影响结果，但是除法不行。这个题目要求对一个大质数取模，原式里面有除法，我们就需要求取除数对于取模数的逆元，然后进行转化为乘法运算。
这样我们就需要先求出\(2\)对于\({10}^9+7\)的逆元\(x^{-1}\)(费马小定理转化一下，快速幂嗯算就完了)
这样计算公式为:
点击查看代码
#include<bits/stdc++.h>
int mod = 1e9+7;
int main()
{
int t = 1;
std::cin >> t;
int tem = (mod + 1) / 2;
while(t--)
{
int x,y;
std::cin >> x >> y;
std::cout << 1ll * (x-y) * tem % mod <<std::endl;
}
return 0;
}
博弈论
点击查看代码
#include<iostream>
const int N = 1e6 + 10;
using namespace std;
int a[N];
int n;
void slove()
{
cin >> n;
for(int i = 0;i <= n;i++)cin >> a[i];
for(int i = n;i > 0;i--)a[i-1] += a[i] / 2;
cout << a[0] << endl;
if(a[0])puts("Alice");
else puts("Bob");
}
int main()
{
int t;
cin >> t;
while(t--)slove();
return 0;
}