注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1101 数据还原  

2012-12-12 14:40:27|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数据还原

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:5            测试通过:3

描述

度度熊近日开发出一种新型随机数生成算法,方法是使用一个质数Pn个非负整数A0A1, …, An-1,生成第m个随机数的公式为

通过适当的选取参数Ai,度度熊发现这种随机数生成的方法具备一种神秘的性质,并帮助他完成了多项研究。度度熊准备在一个新环境中进行他的下一次实验,他让他的助手去取他桌上写着n个整数A0,A1, …, An-1的纸条以产生新的随机数据,取回后度度熊发现助手取回的不是写着参数的纸条,而是他上一次实验时记录下来的随机数randsrands+1,…, rands+n-1,而数的个数正好也是n个。现在度度熊已经没有时间等他的助手再回去取写着参数的纸条了,你能帮度度熊生成接下来的x个随机数(即rands+n,rands+n+1, …, rands+n+x-1)让他继续他的实验么?

输入

输入的第一行包含4个非负整数n, P,s, x,相邻两个整数间用一个空格分隔。

第二行包含n个整数rands, rands+1, …, rands+n-1,表示度度熊上一次实验生成的随机数。

输出

输出一行,包含x个非负整数rands+n, rands+n+1, …, rands+n+x-1,相邻的两个整数间用一个空格分隔,表示接下来生成的x个随机数。

样例输入

4 101 1 2
5 17 43 89

样例输出

60 63

提示

对于100%的数据,1 ≤ n, s, x≤ 1000,s + x < P < 109,P为质数。

题目来源

Baidu Astar 2011

————————————————————————————————————————————

2011年百度之星初赛的第二题,这道题不会做……搜了下,有大牛说是用 高阶等差数列解,百度了下高阶等差数列,然后拿样例推了下,就能找到规律了,还需要注意几个地方

先说下高阶等差数列吧:

百度百科里有详细介绍,定义:对于一个给定的数列,把它的连结两项an+1与an的差an+1-an记为bn,得到一个新数列,把数列bn称为原数列的一阶差数列,如果cn=bn+1-bn,则数列cn是二阶差数列,依此类推,可得出数列的p阶差数列。

高阶等差数列有两条重要的性质:

1. 数列是p阶等差数列的充要条件是:数列的通项是关于n的p次多项式

2. 如果数列是p阶等差数列,则其前n项和Sn是关于n的p+1次多项式

题目中的rands展开后可以看成是n的p次多项式,由此可以利用高阶等差数列进行递推找规律,规律如下:

如样例:

5  17  43  89 / 161  265……

 12  26  46 / 72  104…… //该序列是上一序列相邻两项之差

    14  20 / 26  32…… //该序列是上一序列相邻两项之差

       6 /

161%101=60;265%101=63……

所以,可以由给出的n个数,依次推出各个序列,得到最后的一个数,然后再往回推,就可以推出接下来的x个数。

/*
* fudq.cpp
*
* Created on: 2012-12-12
* bjfuoj-1101
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define N 1010
__int64 a[N],b[N],f[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
__int64 n,P,s,x,i,j,k;
while(scanf("%I64d%I64d%I64d%I64d",&n,&P,&s,&x)!=EOF)
{
for(i=0;i<n;i++)
scanf("%I64d",&a[i]);
k=1;
f[0]=a[n-1];
while(n>1)
{
for(i=0;i<n-1;i++)
b[i]=(P+a[i+1]-a[i])%P;//!!! a[i+1]-a[i]可能是负数
n--;
f[k++]=b[n-1];
for(i=0;i<n;i++)
a[i]=b[i];
}
for(i=0;i<x;i++)
{
for(j=k-2;j>=0;j--)
f[j]=(f[j]+f[j+1])%P;
if(i!=0)
printf(" ");
printf("%I64d",f[0]);
}
printf("\n");
}
return 0;
}


  评论这张
 
阅读(86)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018