首页 > ACM题库 > HDU-杭电 > HDU 3891-Being a Predictor[解题报告]HOJ
2015
04-13

HDU 3891-Being a Predictor[解题报告]HOJ

Being a Predictor

问题描述 :

Let A(x) = Sigma(Ai * x^i) (0<=i<=N-1). Given A(1), A(2),…, A(N), You are asked to calculate A(N+1) mod 112233.
It is guaranteed that A(1), A(2), …, A(N), A(N+1) are all integers.

输入:

There are multiple test cases, ended with an EOF.
For each case:
Line 1 contains a positive integer N (N <= 10^6).
Line 2 to Line N+1: each contains a non-negative integer less than 65536. The integer in Line i is A(i-1).

输出:

There are multiple test cases, ended with an EOF.
For each case:
Line 1 contains a positive integer N (N <= 10^6).
Line 2 to Line N+1: each contains a non-negative integer less than 65536. The integer in Line i is A(i-1).

样例输入:

1
18605
5
19543
19998
12266
27854
2103

样例输出:

18605
110887

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const long long P=112233;
typedef long long ll;
int n;
long long c[P*10],pro,p[20],s[20],a[P*10],inv[P*10];

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
 if ( b==0 ){
 d=a; x=1; y=0;
 }
 else{
 exgcd(b,a%b,d,x,y);
 ll t=x; x=y; y=t-(a/b)*y;
 }
}

void cnt(){
 long long d,x,y;
 for (int i=1;i<=1000001;i++){
 long long a=i;
 exgcd(a,P,d,x,y);
 inv[a]=x;
 }
}

void work(long long a,long long b,int k){
 for (int i=1;i<=4;i++){
 while ( a%p[i]==0 ){
 s[i]++;
 a/=p[i];
 }
 while ( b%p[i]==0 ){
 s[i]--;
 b/=p[i];
 }
 }
 pro=(pro*inv[b]*a)%P;
 c[k]=pro;
 for (int i=1;i<=4;i++)
 for (int j=1;j<=s[i];j++)
 c[k]=c[k]*p[i]%P;
}

int main(){
 cnt();
while ( scanf("%d",&n)!=EOF ){
 for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
 p[1]=3; p[2]=11; p[3]=19; p[4]=179;
 pro=1;
 memset(s,0,sizeof(s));
 c[0]=1;
 int e=1;
 for (int i=1;i<=n;i++)
 work(n-i+1,i,i);
 a[0]=0;
 for (int i=1;i<=n;i++){
 a[0]=(a[0]+c[i]*a[i]*e)%P;
 e=-e;
 }

 memset(s,0,sizeof(s));
 pro=1;
 e=1;
 for (int i=1;i<=n+1;i++)
 work(n-i+2,i,i);
 long long ans=0;
 for (int i=n;i>=0;i--){
 ans=(ans+c[i]*a[i]*e)%P;
// printf("%d %I64d\n",i,c[i]);
 e=-e;
 }
 ans=(ans+P)%P;
 cout<<ans<<endl;
}
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。