| 题目名称 | 1608. [SPOJ 422] 转置更好玩 |
|---|---|
| 输入输出 | transp2.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 8000 ms (8 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 6 |
| 题目来源 |
 cstdio
于2014-04-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：30， 通过率：50% | ||||
 AAAAAAAAAA |
100 | 1.290 s | 27.03 MiB | C++ |
 TA |
100 | 3.003 s | 38.46 MiB | C++ |
 ww944606393 |
100 | 4.978 s | 0.32 MiB | C++ |
 cstdio |
100 | 5.368 s | 0.32 MiB | C++ |
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 6.680 s | 0.32 MiB | C++ |
|
mikumikumi |
100 | 6.775 s | 0.32 MiB | C++ |
|
mikumikumi |
100 | 7.497 s | 0.27 MiB | C++ |
 ljz |
100 | 7.598 s | 16.49 MiB | Pascal |
|
ljz |
100 | 8.205 s | 12.56 MiB | Pascal |
 神利·代目 |
100 | 10.216 s | 35.38 MiB | C++ |
| 关于 转置更好玩 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
少了一个非常重要的hack：a=b=0。。
TA
2016-04-01 09:06
3楼
| ||||
|
《Pólya计数法的应用》这篇论文中给出的题解有一些小错误，需要自行思考&google
| ||||
|
之所以是“更”是因为有一道一模一样只是数据小的题目：SPOJ419……
这题在SPOJ上想过需要各种常数优化，比如不能用vector什么的…… | ||||
【题目描述】
给你一个2^a*2^b的矩阵，在内存中的存放方式是先存第一行的，再存第二行的……每行也是从左到右存放。现在你想把它变成它的转置矩阵（也是一样的储存方式），但是只能用交换操作（即交换两个储存单元的内容），至少需要交换多少步？
【输入格式】
第1行数数据组数c(1<=c<=400000).
接下来有c行，每行一组测试数据：两个整数a,b(0<=a+b<=1000000)。
【输出格式】
对每组数据输出一个整数，即转置矩阵需要的最少交换次数。因为这个次数可能很大，你只需要输出它模1000003的值（没错，这是个素数）。
【样例输入】
3
1 1
2 2
5 7
【样例输出】
1
6
3744
【来源】
Author: Pawel Gawrychowski