首页 > 代码库 > HDU 5139数据离线处理
HDU 5139数据离线处理
此题可以找到规律f(n) = 1! * 2! *...*n!, 如果直接打表的话，由于n比较大(10000000)，所以会超内存，这时候就要用到离线处理数据，就是先把数据存起来，到最后在暴力一遍求解就行了，代码如下
代码一(超内存):
1 #include <stdio.h> 2 3 const long long mod = 1000000007; 4 const int N = 10000007; 5 long long a[N]; 6 7 int main() 8 { 9 a[0] = a[1] = 1;10 for (int i = 2; i < N; i++)11 {12 a[i] = a[i - 1] * i % mod;13 } 14 15 for (int i = 2; i < N; i++)16 {17 a[i] = a[i - 1] * a[i] % mod;18 }19 int n;20 while (~scanf("%d", &n))21 {22 printf("%I64d\n", a[n]);23 }24 return 0;25 }
代码二(AC)
1 #include <stdio.h> 2 #include <vector> 3 #include <map> 4 const long long mod = 1000000007; 5 using namespace std; 6 7 int main() 8 { 9 int n;10 vector<int> a;11 map<int, long long> vis;12 while (scanf("%d", &n) != EOF)13 {14 a.push_back(n);15 vis[n] = -1;16 }17 long long prep = 1, nowp, prea = 1, nowa;18 for (int i = 1; i <= 10000000; i++)//离线算法 19 {20 nowp = prep * i % mod;//相当于求阶乘 21 prep = nowp;22 nowa = nowp * prea % mod;//求n个阶乘的乘积 23 prea = nowa;24 if (vis.count(i))25 {26 vis[i] = nowa;27 }28 } 29 for (int i = 0; i < a.size(); i++)//暴力一遍 30 {31 32 printf("%I64d\n", vis[a[i]]);33 }34 return 0;35 }
离线算法确实挺神奇的，要深刻理解才能做题
HDU 5139数据离线处理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。