51nod 算法马拉松4 B递归(YY)
2024-10-18 22:37:09
函数f(n,m)
{
若n=1或m=1返回a[n][m];
返回f(n-1,m)异或f(n,m-1);
}
读入2<=n,m<=100
for i=2->100读入a[1][i]
for i=2->100读入a[i][1]
输出f(n,m)
发现当n,m较大时程序变得异常缓慢。
小b经过一番思考,很快解决了这个问题。
这时小c出现了,我将n,m都增加131072,你还能解决吗?
相对的,我会读入2->131172的所有a[1][i]和a[i][1]。
小b犯了难,所以来找你,你能帮帮他吗?
Input
第一行读入131171个正整数,表示i=2->131172的a[1][i](1<=a[1][i]<=1000000000)。
第二行读入131171个正整数,表示i=2->131172的a[i][1](1<=a[i][1]<=1000000000)。
第三行读入一个正整数Q(1<=Q<=10000),表示询问的次数。
接下来Q行,每行两个数n,m(2<=n,m<=100),表示每一组询问。
Output
Q行,每行为f(n+131072,m+131072)
Input示例
2 3 4 5 6 7 8 … 131171 131172
2 3 4 5 6 7 8 … 131171 131172
3
2 2
2 3
2 4
Output示例
0
0
131072 考虑一个点(0, 0)对某一个点(n, m)的贡献次数为C(c + m, n),所以这里在计算f(n, m)时,只要知道第一行和第一列的每个数贡献的次数是基奇数此还是偶数次,也就是计算C(n+m, m)是奇数还是偶数, 那么只要知道n!里的2的个数G(n),那么如果有G(n + m) = G(n) + G(m),此时这个组合数就是偶数,否则为奇数。
由于f(n, m) = f(n - 1, m) + f(n, m - 1),只要知道对于f(131074, 131074...131172)与f(131074...131172, 131074)的每个值就好了(其他的可以由这些推过来)
#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf (-((LL)1<<40))
#define lson k<<1, L, (L + R)>>1
#define rson k<<1|1, ((L + R)>>1) + 1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define dec(i, a, b) for(int i = a; i >= b; i --) //typedef __int64 LL;
typedef long long LL;
typedef pair<int, int> Pair;
const int MAXN = + ;
const int MAXM = ;
const double eps = 1e-;
LL MOD = ; const int N = ;
const LL mod = ; int f[];
int ans[][];
int r[], c[]; void init(int n) {
f[] = f[] = ;
rep (i, , n) {
int num = , x = i;
while(x % == ) num++, x /= ;
f[i] = f[i - ] + num;
}
} int judge(int n, int m) {
return f[n] == f[m] + f[n - m];
} int calc(int n, int m) {
int ans = ;
rep (i, , m) ans ^= c[i] * judge(n - + m - i, m - i);
rep (i, , n) ans ^= r[i] * judge(n - i + m - , m - );
return ans;
} int main()
{
//FIN;
//FOUT;
init();
rep (i, , ) scanf("%d", &c[i]);
rep (i, , ) scanf("%d", &r[i]);
rep (i, , ) ans[][i - ] = calc(, i);
rep (i, , ) ans[i - ][] = calc(i, );
rep (i, , ) {
rep (j, , ) {
ans[i][j] = ans[i - ][j] ^ ans[i][j - ];
}
}
int q, n, m;
cin >> q;
while(q --) {
scanf("%d %d", &n, &m);
printf("%d\n", ans[n][m]);
}
return ;
}
最新文章
- Eclipse使用多个Console
- apktool反编译apk文件
- Visual Studio 2012下Box2D开发环境设置
- CURL的使用<;发送与接收数据>;
- SQLite入门与分析(八)---存储模型(2)
- sys.argv[]用法
- objective-c 加号 减号 - +
- ajax get/post
- UVA 10954 Add All
- js函数的一些技巧
- 浙大pat 1054 题解
- Floyd算法(最短路)
- IDEA快捷键积累
- Ubuntu 14.04 mame sound fix
- PLSQL安装、PLSQL汉化、激活
- alpha阶段的 postmortem 报告
- Java 虚拟机:互斥同步、锁优化及synchronized和volatile
- Autotools使用流程【转】
- curl常用功能
- IOS UIImage两种初始化的区别
热门文章
- MyBatis—mybatis-config.xml配置介绍
- VS2010/MFC编程入门之二十一(常用控件:编辑框Edit Control)
- CCPC-Wannafly Winter Camp Day2 (Div2, onsite)
- python 解析xml遇到xml.etree.ElementTree.ParseError: not well-formed (invalid token): line 4, column 34
- mongodb的分片
- @Tranactional事务没有回滚
- 微信小程序:工具配置 project.config.json
- Java的初始化与清理
- FZU 1901 Period II(KMP中的next)题解
- Firefox管理已经保存的账号和密码