首页 > 代码库 > hdu--5139--bc
hdu--5139--bc
这题 很多人用的都是 离线处理的方法。
比赛的时候 就没想到这个方法。
一直在mle tle之间徘徊。。 porker的这个处理数组方法很好
我本来是1-1e7的数组范围存下的是每个f[n]的值
现在我用一个 1-1e6的数组来表示f[n] , g[n] g[n]就是n的阶乘
因为 f[n] = f[n-1] * g[n]
那么当我的数组范围是开到1e6的时候 就是说0存的是n=1的解 1存的是n=10的解 10 存的是n=100的解 11存的是n=110的解
那么你可以发现 我任意一个要查询的数n 都将落在[n/10,n/10+1)这个区间内的某个数之内 就是说15会在[1,2)之间
45会在[4,5)之内。
这种方法不仅适用于本题 对于某些对内存要求很高的 同时你的方法足够满足这个时间的情况下 可以这样来解决
同时 这边你的数组最好开成int来计算 虽然当我们进行上面步骤之后 也不会mle 但是为了保险开成int来保存
但是 中途计算的时候 会爆 int所以我们需要先转换为LL 最后计算完成之后在强制转换为int
ok 贴下代码 离线的明天再贴 打游戏啦。。
1 #include <iostream> 2 using namespace std; 3 4 typedef __int64 LL; 5 const int size = 10000010; 6 const int mod = 1000000007; 7 LL n; 8 int f[1000010]; 9 int g[1000010];10 11 void init( )12 {13 f[0] = g[0] = 1;14 int now , next;15 now = 1;16 int sum , ans;17 sum = 1;18 for( int i = 2 ; i<=size-9 ; i++ )19 {20 next = (int)( ( 1LL * ( now%mod ) * i ) % mod);21 ans = (int)( ( 1LL * (sum%mod) * (next%mod) ) % mod);22 now = next;23 sum = ans;24 if( i%10==0 )25 {26 f[i/10] = ans;27 g[i/10] = next; 28 }29 }30 }31 32 int main()33 {34 init( );35 LL temp , sum , ans , now , next;36 while( ~scanf("%d",&n) )37 {38 if( n%10==0 )39 {40 printf( "%d\n",f[n/10] );41 }42 else43 {44 temp = n/10;45 ans = 1LL * f[n/10];46 sum = ans;47 now = 1LL * g[n/10];48 for( LL i = temp*10+1 ; i<=n ; i++ )49 {50 next = (int)( ( now%mod ) * i % mod );51 ans = (int)( (sum%mod) * (next%mod) % mod );52 now = next;53 sum = ans;54 }55 printf( "%I64d\n",ans);56 }57 }58 return 0;59 }
hdu--5139--bc
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。