还是整理下题目，回顾下见过的有启发的题吧。
回忆：a^n = a^(n%(m-1)) (%m)
hdoj 4810 Wall Painting
题意：给定n个数，进行n次操作。对第i次操作，要求你从n个数里面任选i个数，用这i个数异或得到一个新数，并把所有新数相加（可以重复加）。对每次操作，输出新数相加之和。
来自：https://blog.csdn.net/qingshui23/article/details/52599936
解题思路：
首先将每一个数的二进制求出来，在每一位二进制数中求出 1 的个数，拿样例来说吧。
1 = 0 0 0 1
2 = 0 0 1 0
10= 1 0 1 0
1 = 0 0 0 1
每次选奇数个 1 和 剩余的选的个数-1 个 00， 比如说求任意两个数的异或和，那么我们选 1个 1 ，选 2−1 个 0， 我们肯定选奇数个 1， 因为偶数个 1 异或还是 0 没有意义，然后就是组合数了， 从当前的 1 的总个数里面选择奇数个 1 ,在乘以相应的 2^x次幂，(c[cnt[j]][k]∗c[(n−cnt[j])][i−k])∗(2j)其中 cnt[j] 表示的是第 j 位 11 的总个数， k表示的是要选择的 1 的个数。i表示的
我的理解就是按位分开讨论加和，讨论出不为0的情况值加和。
代码来自：https://blog.csdn.net/chenzhenyu123456/article/details/49819051
int num[40];
LL C[1010][1010];
void getC()
{
for(int i = 0; i <= 1000; i++)
C[i][0] = 1;
for(int i = 1; i <= 1000; i++)
for(int j = 1; j <= i; j++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}
int main()
{
getC();
int n;
while(Ri(n) != EOF)
{
CLR(num, 0);
for(int i = 1; i <= n; i++)
{
LL a; Rl(a);
for(int j = 0; j <= 35; j++)
if(a & (1LL<<j))
num[j]++;
}
for(int i = 1; i <= n; i++)
{
LL cnt = 0;
for(int j = 0; j <= 35; j++)//第j位的1
{
if(num[j] == 0) continue;
for(int k = 1; k <= i && k <= num[j]; k+=2)//选k个1 k为奇数时异或才加
{
if(n-num[j] >= i-k)
{
cnt += C[num[j]][k] * ((1LL<<j) % MOD) % MOD * C[n-num[j]][i-k] % MOD;
cnt %= MOD;
}
}
}
if(i > 1)
printf(" ");
printf("%lld", cnt);
}
printf("\n");
}
return 0;
}
Codeforces 615D Multipliers
题意：给定m个质因子p[]，有p[1]*p[2]*...*p[m] == n，问n所有因子的乘积 % 1e9 + 7。
来自：https://blog.csdn.net/chenzhenyu123456/article/details/50486219
思路：组合数学。
先把所有因子存起来，并统计个数为top（不相同的）。考虑每个质因子rec[i]做出的贡献，结果为rec[i]^num。其中num为rec[i]在n所有因子乘积中存在的个数。定义1-i质因子的组合方案数l[i]，后i-top个质因子的组合方案数r[i]。
考虑第i个质因子的状态，取或不取，不取有l[i-1]，取则有l[i-1] * cnt[rec[i]]（可能取1 - cnt[rec[i]]）同理求法r[]。
对于一个质因子rec[i]，可以与前、后组合，那么它的可组合方案数为temp = l[i-1] * r[i+1]。若该质因子有Num个，则有方案rec[i] * temp 、rec[i] * rec[i] * temp... rec[i]^(Num) * temp。统计rec[i]出现次数有num = (Num+1) * Num/2 * temp.下面ans *= rec[i] ^ num就好了。
num值很大，费马小定理a^n = a^(n%(m-1)) (%m)搞下就ok了。也就是说num % (1e9+7-1)。
还能说什么，膜拜大神。。。
LL pow_mod(LL a, LL n)
{
LL ans = 1;
while(n)
{
if(n & 1LL)
ans = ans * a % MOD;
a = a * a % MOD;
n >>= 1;
}
return ans;
}
LL l[MAXN], r[MAXN];
LL cnt[MAXN];
int rec[MAXN];
int main()
{
int m; Ri(m);
int top = 0;
for(int i = 1; i <= m; i++)
{
int a; Ri(a);
if(!cnt[a])
rec[++top] = a;
cnt[a]++;
}
l[0] = r[top+1] = 1;
for(int i = 1; i <= top; i++)
l[i] = l[i-1] * (cnt[rec[i]] + 1) % (MOD-1);
for(int i = top; i >= 1; i--)
r[i] = r[i+1] * (cnt[rec[i]] + 1) % (MOD-1);
LL ans = 1;
for(int i = 1; i <= top; i++)
{
LL Num = cnt[rec[i]];
if(Num)
{
LL num = l[i-1] * r[i+1] % (MOD-1);
num = (Num + 1) * Num / 2 % (MOD-1) * num % (MOD-1);
ans = ans * pow_mod(rec[i], num) % MOD;
}
}
Pl(ans);
return 0;
}
Codeforces E. Qwerty78 Trip
n*m的格子，其中有一个格子是坏的，问你从(1, 1) - (n, m)有多少种走法。
来自：https://blog.csdn.net/chenzhenyu123456/article/details/51545532
填满n * m的矩阵，发现这就是一个杨辉三角的组合数问题。
在格子没有坏的情况下，(1, 1) - (n, m)的走法dp[1][1][n][m] = C(n+m-2, m-1)。
当(x, y)坏的情况下，少出的情况就是dp[1][1][x][y] * dp[x][y][n][m]。
我们把(x, y)看做(1, 1)然后求一下就好了。套个逆元。
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 2 * 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
void add(LL &x, LL y) { x += y; x %= MOD; }
LL pow_mod(LL a, int n) {
LL ans = 1;
while(n) {
if(n & 1) {
ans = ans * a % MOD;
}
a = a * a % MOD;
n >>= 1;
}
return ans;
}
LL f[MAXN];
LL C(int n, int m) {
return f[n] * pow_mod(f[n-m], MOD-2) % MOD * pow_mod(f[m], MOD-2) % MOD;
}
int n, m;
int main()
{
f[0] = 1LL;
for(int i = 1; i <= 200000; i++) {
f[i] = f[i-1] * i % MOD;
}
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
int x, y; scanf("%d%d", &x, &y);
if(x == 1 && y == 1) {
printf("0\n");
continue;
}
printf("%lld\n", (C(n+m-2, m-1) - C(n+m-(x-1)-(y-1)-2, m-(y-1)-1) * C(x+y-2, y-1) % MOD + MOD) % MOD);
}
return 0;
}
CodeForces - 16C
题目大意：给你原始尺寸a：b 和 目标比例x：y ， 问面积最大的长a和宽b。
来自：https://blog.csdn.net/qq_24477135/article/details/52789168
思路：首先要化简x:y，因为4:3肯定是8:6.（很重要）
其次，要开longlong。
1、如果化简后的比例比x或y大，显然不可以
2、然后就是讨论bx和ay谁比较大就可以了，前者大，按x分，否则按y分。
LL a , b , x , y;
LL gcd(LL a , LL b)
{
if(b == 0) return a;
else return gcd(b , a % b);
}
int main()
{
while(scanf("%I64d %I64d %I64d %I64d" , &a , &b , &x , &y) != EOF)
{
LL g = gcd(x , y);
x /= g;
y /= g;
LL t1 = a / x;
LL t2 = b / y;
if(a < x || b < y)
{
printf("0 0\n");
}
else if(b * x > a * y)
{
printf("%I64d %I64d\n" , t1 * x , t1 * y);
}
else if(b * x < a * y)
{
printf("%I64d %I64d\n" , t2 * x , t2 * y);
}
else
printf("%I64d %I64d\n" , a , b);
}
return 0;
}