admin管理员组文章数量:1487745
英雄会第二届在线编程大赛·线上初赛：AB 题解
给定两个正整数a,b，分别定义两个集合L和R，
集合L：即把1~a，1~b中整数乘积的集合定义为L = {x * y | x,y是整数且1 <= x <=a , 1 <= y <= b}；
集合R：1~a，1~b中整数异或的集合定义为集合R = {x ^ y | x,y是整数且1 <= x <=a , 1 <= y <= b}，其中^表示异或运算。
现从L中任取一个整数作为A，从R中任取一个整数作为B，如果必要在B的左边补0，使得B达到：“b的位数+1”位（十进制），然后把B接到A的右边，形成的一个十进制数AB。求所有这样形成数的和。
输入a,b 1<=a<=30, 1<=b<=10000000。
输出所有产生的AB数的和，由于结果比较大，输出对1000000007取余数的结果。
例如：a = 2, b = 4，
则L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} = {1, 2, 3, 4, 6, 8}
R = {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} = {0, 1, 2, 3, 5, 6}
相接的时候保证R中的数至少有两位，所以相接后所有的AB数的集合是
{
100, 101, 102, 103, 105, 106,
200, 201, 202, 203, 205, 206,
300, 301, 302, 303, 305, 306,
400, 401, 402, 403, 405, 406,
600, 601, 602, 603, 605, 606,
800, 801, 802, 803, 805, 806
}
输出它们的和：14502。
题目分析：
这其实算两个题，这么整齐的矩阵实际上主要就是Sum(L)和Sum(R).
求这两个部分都是独立的。所以拆成2个题也没什么问题。
最后的结果result=Sum(L)*Count(R)*Len(p)+Sum(R)*Count(L);
Len(p)简单就是个Pow(10,"b的位数+1")
public static int Len(int b) { int len = 100; while (b/10 > 0) { len = len*10; b = b/10; } return len; }
- 这题一眼看上去，暴力肯定是可以实现的。
var aa = new bool[a*b+1];
var bb = new bool[a + b + 1];
Int64 len = Len(b);
Int64 result1 = 0;
Int64 result2 = 0;
int size1 = 0;
int size2 = 0;
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
if (!aa[i*j])
{
result1 += ((i*j))%MOD;
size1++;
aa[i*j] = true;
}
if (!bb[i ^ j])
{
result2 += (i ^ j)%MOD;
size2++;
bb[i ^ j] = true;
}
}
}
result1 = (result1%MOD)*(len%MOD);
result1 = (result1%MOD)*(size2%MOD);
result2 = (result2%MOD)*(size1%MOD);
return (int) ((result1 + result2)%MOD);- 优化
但是暴力，算一个run(30,10000000)就会超过3秒了
1.先优化 XOR 吧
这个还算比较简单
因为a<=30。把b分为很多段。
00001-11111
1 00000
1 11111
。。
X..X 00000
X..X 11111
Y..Y 00000
b
显然，对于b<=31的部分，直接暴力算效率也没问题。而对于
X..X 00000
X..X 11111
这种，直接算X..X乘以a与00000-11111 XOR的结果就行了。
最后多出来的一段
Y..Y 00000
b
数据量不会超过31，暴力吧。
如果a更小的话，可以按000-111之类做更细的分解。但是基本按11111分解的效率就足够了。这个代码写得有点啰嗦，基本原理应该是对的。
代码语言：javascript代码运行次数：0运行复制private static void DoXor(int a, int b)
{
var bb = new bool[a + b + 1];
if (b <= 31)
{
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
if (!bb[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
bb[i ^ j] = true;
}
}
}
return;
}
int k = b/32 - 1;
int m = (k + 1)*32;
if ((b & 31) == 31)
{
k = k + 1;
m = b + 1;
}
Int64 sum2kk = 0;
Int64 count2kk = 0;
for (int i = 1; i <= a; i++)
{
for (int j = 0; j <= 31; j++)
{
if (!bb[i ^ j])
{
sum2kk += (i ^ j)%MOD;
count2kk++;
bb[i ^ j] = true;
}
}
}
count2 += (count2kk*k);
sum2 += (sum2kk*k)%MOD;
sum2 += count2kk*(k + 1)*k*(32/2)%MOD;
for (int j = m; j <= b; j++)
{
for (int i = 1; i <= a; i++)
{
if (!bb[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
bb[i ^ j] = true;
}
}
}
var kk = new bool[32 + a + 1];
for (int j = 1; j <= 31; j++)
{
for (int i = 1; i <= a; i++)
{
if (!kk[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
kk[i ^ j] = true;
}
}
}
}2.Sum(L)的优化
把a*b的结果也分为a段
1->b
b+1->2b
...
kb+1->(k+1)b
...
(a-1)b+1->ab
显然对于(k-1)b+1->kb这个区间
只有(k->a)*b才会出现。
所以 (k-1)b+1->kb区间内，所以能被（k->a）整除的都在集合L里。
对于 (k-1)b+1->kb区间内，能被m整除的数的Count和Sum是很容易求的。
很简单的思路就是计算Count(k),Count(k+1)..Count(a)
但是这里有个重复的问题。比如k->a为3->8
能被6整除的肯定能被3整除，所以算了Count(3)就不用算Count(6)
于是开始求从k->a不包含倍数关系的集合
3->8
为3，4，5，7
算完Count(3)+Count(4)+Count(5)+Count(7)。
但是12在Count(3)的时候算了，在Count(4)的时候也算了。
于是 Count(3)+Count(4)+Count(5)+Count(7)-Count(3*4)-Count(3*5)-Count(3*7)....+Count(3*4*5).....-Count(3*4*5*7)
实际计算的时候其实Count里面还要算gcd。
做完提交后才有人在群里面说这个是 容斥原理 。
代码语言：javascript代码运行次数：0运行复制 private const int MOD = 1000000007;
private static Int64 count1 = 0;
private static Int64 count2 = 0;
private static Int64 sum1 = 0;
private static Int64 sum2 = 0;
public static int Len(int b)
{
int len = 100;
while(b/10>0)
{
len = len*10;
b = b / 10;
}
return len;
}
private static Int64 gcd2(Int64 a, Int64 b)
{
if (b == 0) return a;
return gcd2(b, a % b);
}
private static List<int> ValidNum(int a, int k)
{
List<int> result = new List<int>();
result.Add(k);
bool bFlag = true;
for (int i = k+1; i <= a; i++ )
{
bFlag = true;
foreach (int kk in result)
{
if (i % kk == 0)
{
bFlag = false;
break;
}
}
if (bFlag)
{
result.Add(i);
}
}
return result;
}
private static void CalcSeg(Int64 k, Int64 b, Int64 m, bool add)
{
if (m < k ||m > k*b) return;
Int64 start = ((k - 1) * b + 1) / m + 1;
if (((k-1)*b+1)%m==0)
start = ((k - 1) * b + 1) / m;
Int64 end = k * b / m;
if (add)
{
sum1 += ((start + end) * (end - start + 1) * m / 2) % MOD;
count1 += end - start + 1;
}
else
{
sum1 -= ((start + end) * (end - start + 1) * m / 2) % MOD;
if (sum1 < 0)
sum1 += MOD;
count1 -= end - start + 1;
}
}
public static int run(int a, int b)
{
count1 = count2 = sum1 = sum2 = 0;
bool[] bb = new bool[a + b + 1];
Int64 len = Len(b);
for (int i = 1; i <= a; i++ )
{
List<int> nums = ValidNum(a,i);
int nn = nums.Count;
int[] digit = new int[nn];
int ii,jj;
while (true)//这其实是一个求1-n的全部非空集合的一个模板
{
for (ii = 0; ii < nn && digit[ii] == 1; digit[ii] = 0, ii++) ;
if (ii == nn)
break;
else
digit[ii] = 1;
for (ii = 0; ii < nn && digit[ii] == 0; ii++) ;
int c = 1;
Int64 mul = nums[ii];
for (jj = ii + 1; jj < nn; jj++)
{
if (digit[jj] == 1)
{
mul = (nums[jj] * mul) / gcd2(nums[jj], mul);//太耗时
c++;
}
}
CalcSeg(i, b, mul, c % 2 == 1);
}
}
DoXor(a,b);
sum1 = (sum1 % MOD) * (len % MOD);
sum1 = (sum1 % MOD) * (count2 % MOD);
sum2 = (sum2 % MOD) * (count1 % MOD);
return (int)((sum1 + sum2) % MOD);
}运行了一下，总算在1秒以下了。但是还是慢，用工具分析了一下，发现计算gcd花费的时间太多了。
又费了不少脑细胞，用递归把每个区间内的gcd重复计算的情况减少了很多。
最后看着代码 接近200行 。。。应该有 更简单 的方法吧。。
代码语言：javascript代码运行次数：0运行复制 private const int MOD = 1000000007;
private static Int64 count1;
private static Int64 count2;
private static Int64 sum1;
private static Int64 sum2;
public static int Len(int b)
{
int len = 100;
while (b/10 > 0)
{
len = len*10;
b = b/10;
}
return len;
}
private static Int64 gcd2(Int64 a, Int64 b)
{
if (b == 0) return a;
return gcd2(b, a%b);
}
private static List<int> ValidNum(int a, int k)
{
var result = new List<int>();
result.Add(k);
bool bFlag = true;
for (int i = k + 1; i <= a; i++)
{
bFlag = true;
foreach (int kk in result)
{
if (i%kk == 0)
{
bFlag = false;
break;
}
}
if (bFlag)
{
result.Add(i);
}
}
return result;
}
private static void CalcSeg(Int64 k, Int64 b, Int64 m, bool add)
{
if (m < k || m > k*b)
{
return;
}
Int64 start = ((k - 1)*b + 1)/m + 1;
if (((k - 1)*b + 1)%m == 0)
start = ((k - 1)*b + 1)/m;
Int64 end = k*b/m;
if (add)
{
sum1 += ((start + end)*(end - start + 1)*m/2)%MOD;
count1 += end - start + 1;
}
else
{
sum1 -= ((start + end)*(end - start + 1)*m/2)%MOD;
if (sum1 < 0)
sum1 += MOD;
count1 -= end - start + 1;
}
}
private static void DoAdd(List<int> nums, int lastkk, Int64 pregcd, int lastn, int n, int i, int b)
{
if (lastn == n)
{
return;
}
for (int m = lastkk + 1; m <= n; m++)
{
Int64 newPregcd = pregcd*nums[m - 1]/gcd2(pregcd, nums[m - 1]);//gcd(a,b,c,d)，gcd(a,b,c,e)的时候，pregcd就是gcd(a,b,c),这相当于一个缓存
CalcSeg(i, b, newPregcd, lastn%2 == 0);
DoAdd(nums, m, newPregcd, lastn + 1, n, i, b);//递归
}
}
private static void DoXor(int a, int b)//啰嗦，可以简化一些代码的
{
var bb = new bool[a + b + 1];
if (b <= 31)
{
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
if (!bb[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
bb[i ^ j] = true;
}
}
}
return;
}
int k = b/32 - 1;
int m = (k + 1)*32;
if ((b & 31) == 31)
{
k = k + 1;
m = b + 1;
}
Int64 sum2kk = 0;
Int64 count2kk = 0;
for (int i = 1; i <= a; i++)
{
for (int j = 0; j <= 31; j++)
{
if (!bb[i ^ j])
{
sum2kk += (i ^ j)%MOD;
count2kk++;
bb[i ^ j] = true;
}
}
}
count2 += (count2kk*k);
sum2 += (sum2kk*k)%MOD;
sum2 += count2kk*(k + 1)*k*(32/2)%MOD;
for (int j = m; j <= b; j++)
{
for (int i = 1; i <= a; i++)
{
if (!bb[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
bb[i ^ j] = true;
}
}
}
var kk = new bool[32 + a + 1];
for (int j = 1; j <= 31; j++)
{
for (int i = 1; i <= a; i++)
{
if (!kk[i ^ j])
{
sum2 += (i ^ j)%MOD;
count2++;
kk[i ^ j] = true;
}
}
}
}
public static int run(int a, int b)
{
count1 = count2 = sum1 = sum2 = 0;
var bb = new bool[a + b + 1];
Int64 len = Len(b);
for (int i = 1; i <= a; i++)
{
List<int> nums = ValidNum(a, i);
DoAdd(nums, 0, 1, 0, nums.Count, i, b);
}
DoXor(a, b);
sum1 = (sum1%MOD)*(len%MOD);
Console.WriteLine(sum1 + " " + count1 + " " + sum2 + " " + count2);
sum1 = (sum1%MOD)*(count2%MOD);
sum2 = (sum2%MOD)*(count1%MOD);
return (int) ((sum1 + sum2)%MOD);
}本文标签： 英雄会第二届在线编程大赛线上初赛AB 题解
版权声明：本文标题：英雄会第二届在线编程大赛·线上初赛：AB 题解 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/shuma/1754903284a3181074.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论