3. MT2293 赌石

（1）题目描述
富饶的璃月街道上有一家石料店，店主小码哥是个精明的商人，为了使他的赌石生意更加红火，他根据赌徒的心理设计了一个有趣的买卖规则:他在店铺的两边放了个小桶，一个桶里有n个红球，另一个有n个蓝球。每一批2n个璞石与这些球一—对应，对每个来买璞石的客户石头都会让他们在原地闭眼旋转数圈后走向一个小桶，若拿到蓝球则可免费获得一块石头，但若拿到红球则需要付出两倍的价钱。

假设每个人每次拿到蓝球和红球的概率相同，现在请你求出一个桶里没球而另一个桶里还剩两个球的概率，精确到小数点后四位。

格式

输入格式: 输入一个正整数代表这批璞石的个数。
.
输出格式: 输出一个四位小数代表所求答案。

样例1

输入格式: 256
.
输出格式: 0.9500

（2）参考代码

#include 
#include 
#include 
#include using namespace std;typedef long double LD;LD C_div(int k, int n)
{LD res = 1;for (int i = n, j = 1; j <= k; i -- , j ++ )res = res * i / j;for (int i = 1; i <= k; i ++ ) res /= (LD)4.0;return res;
}int main()
{int n;cin >> n;n /= 2;printf("%.4llf", 1 - C_div(n - 1, 2 * n - 2));return 0;
}

4. MT2294 square

（1）题目描述
猩猩，骆驼，还有泡泡经常喜欢在饭后到操场上散步，由于猩猩的走路姿势最突出最显眼，理所应当的成为他们中的主角，所以我的题目就说猩猩散步了。(骆驼和泡泡别有意见哈，和猩猩争啥…)

当然，话说回来，猩猩在OI上的能力也是不容低估的，你看，散步时还会想一道与此相关的问题，这是道经典的不能再经典的问题了。

在一个mxn的矩阵上，猩猩在左下角的顶点出现了，他只能沿着路径向上或者向右走，他的目标是“蠕动”到右上角的顶点，问他有多少路径可以选择。嗯，这个、这个、这个似乎地球人都知道怎么做，但是请注意，我有个条件没给呢! m和n现在的最大范围是50000，这可怎么办?仔细想想吧。

格式

输入格式:
只有一行，包含两个整数m和n，其均不小于4，上限均为50000。
.
输出格式: 由于最后的答案数目过大，所以只检查后100位，输出时每行十个数字，没空格间隔，共十行，如果答案位数没超过100位，则需要在空位上补0。

样例1：

输入： 7 4
.
输出：
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000330

（2）参考代码

#include 
using namespace std;
const int N = 1e6 + 7;
int ans[110];
int cnt[N];
int b[110];
void multi(int x)
{memcpy(b, ans, sizeof b);memset(ans, 0, sizeof ans);int j = 0;while (x) {int z = x % 10;x /= 10;for (int i = 1; i <= 100; i++) {if (i + j <= 100)ans[i + j] += z * b[i];}j++;}for (int i = 1; i <= 100; i++) {ans[i + 1] += ans[i] / 10;ans[i] %= 10;}
}
int main()
{int m, n;cin >> m >> n;if (m > n)swap(m, n);for (int i = 0; i < m; i++) {int x = m + n - i;for (int j = 2; j <= x / j; j++) {while (x % j == 0) {x /= j;cnt[j]++;}}if (x != 1)cnt[x]++;}for (int i = 1; i <= m; i++) {int x = i;for (int j = 2; j <= x / j; j++) {while (x % j == 0) {x /= j;cnt[j]--;}}if (x != 1)cnt[x]--;}ans[1] = 1;for (int i = 1; i < N; i++) {while (cnt[i]) {multi(i);cnt[i]--;}}for (int i = 100; i >= 1; i--) {cout << ans[i];if (i % 10 == 1)cout << endl;}return 0;
}

5. MT2295 越狱

（1）题目描述
监狱有n个房间，每个房间关押一个犯人，有m种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对1007取模。

格式

输入格式: 输入只有一行两个整数，分别代表宗教数m 和房间数n。
.
输出格式: 输出一行一个整数代表答案。

样例1

输入格式: 2 3
.
输出格式: 6

备注：

其中: 1≤m ≤le8,1 ≤n ≤1e10

（2）参考代码

#include 
/*
思路：不越狱的状态好计算所以：越狱数=总的状态数-不越狱的状态数
其中 总的状态数为：m^n不越狱的状态数： m*（m-1）^(n-1) :只有第一个可以选择m个宗教，其他的只能选和前一个不同的宗教所以是m-1种情况
这里计算用了快速幂的方法。
*/
using namespace std;
long long p=1007;
long long qpow(long long x, long long y){if(y==0)return 1;if(y%2==1){return qpow(x, y - 1) * x % p;}else{long long t = qpow(x, y/2) % p;return t*t % p;}
}
int main( )
{long long m,n;cin>>m>>n;long long ans = qpow(m,n)-(m*qpow(m-1,n-1)%p);cout<<(ans+p)%p<