原题：L先生与质数V4 原题大意L先生想求出第n个质数（素数）是多少，你能帮助他吗？ 算法分析Meisell-Lehmer算法求素数 http://blog.csdn.net/nemaleswang/article/details/52582684 程序代码#include <bits/stdtr1c++.h> #define MAXN 100 #define MAXM 10001 #define MAXP 40000 #define MAX 400000 #define clr(ar) memset(ar, 0, sizeof(ar)) #define read() freopen("lol.txt", "r", stdin) #define dbg(x) cout << #x << " = " << x << endl #define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) & ...

原题：L先生的回信 原题大意L先生打算回复来自朋友Z的上一封信，可是他担心信的内容在网络传送过程中出现错误，于是打算采用CRC校验方式保证信息完整性，可是他不知道应该怎么做，请你为他求出应该发送的比特序列。 循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)2^R），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)2^R 除以(模2除法)生成多项式G(x)得到的余数就是校验码。 Input多组测试例，处理到文件结束。（测试例<5） 每行有两个字符串，用空格隔开，分别为信的内容和生成多项式（长度<=50）。信的内容为二进制表示。生成多项式可能用x的多项式,也可能用二进制表示(格式见样例)。 Output每行输出一个加入CRC后发送 ...

原题：qwb与二叉树 原题大意对于一棵n个无编号节点，m个叶子的有根二叉树，有多少种形态呐？你能告诉他吗？ 算法分析 http://blog.csdn.net/howardemily/article/details/72871260 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; ll dp[55][55]; int n,m; ll dfs(int x, int y){ ll &ans = dp[x][y]; if(ans != -1) return ans; ans = 0; for(int i = 0; i <= x-1; i++) for(int j = 0; j <= i && j <= y; j++){ ans += dfs(i,j) * dfs(x-i-1,y-j); ans %= mo ...

原题：qwb与整数对 原题大意给出两个整数n和m，请统计满足0＜a＜b＜n并且使得 (a2+b2+m)/(ab) 的结果是整数的整数对(a,b)的个数。 本题包含多组测试例 。当测试例数据是n=m=0时，表示输入结束。（测试例数量<6000）每个测试例一行，是两个整数n和m。输入保证0≤n≤1000，-20000 < m < 20000。 算法分析case=1的时候很容易可以想到一个n^2的暴力那么在case比较大的时候，把所有case根据n的数值进行排序。再离线处理，枚举每一组(a,b)，穷举整数t∈[-20000,20000]，当符合条件(a^2+b^2+t)%ab==0时，ans[t]++，最后根据case的顺序从离线处理中获取答案，复杂度O(∑(i=1..n,j=2..n) (40000/ab)) + O(n^1.5) 程序代码#include <bits/stdc++.h> using namespace std; int n[10100], m[10100]; int ret[10100]; vector<int> id[40404 ...

原题：qwb又偷懒了 原题大意qwb最近在做一个群众收入统计。ta非常懒，以至于忘记了今天领导要来视察。所以急忙催下属去做统计。在接下来长度为n的时间里,每个单位时间都有事情发生,可能会发下以下两种事件： 1)下属递交了一份调查报告，由于太匆忙，上面只有一个整数x，代表一个居民的收入。2)领导来视察了，领导会来询问，收入在区间[l,r]内的居民的平均收入，qwb需要给出回答。 qwb非常讨厌小数，所以qwb上报时都会省略小数部分。如果上报时统计的人数为0，qwb就暴露了他偷懒的事情，他就会zhizhiwuwu。 算法分析用两个树状数组分别保存收入和人数，坑点在收入为0的情况，可以记录一下0的个数，或者直接平移1。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; const ll maxn = 1000000+100; ll c1[maxn],c2[maxn]; ll lowbit(ll x){ return x & ( ...