| 记录编号 |
159375 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[CQOI2015]多项式 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.295 s |
| 提交时间 |
2015-04-21 07:28:09 |
内存使用 |
0.38 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEL=5010,BASE=10000,BASEL=4;
class HPint{
public:
int n;
int s[SIZEL];
HPint(){n=1;memset(s,0,sizeof(s));}
//要求时刻保持无用位全0
void print(void)const{
printf("%d",s[n-1]);
for(int i=n-2;i>=0;i--) printf("%04d",s[i]);
}
void operator = (char str[]){
static int pow_10[10]={1};
for(int i=1;i<BASEL;i++) pow_10[i]=pow_10[i-1]*10;
int L=strlen(str);
n=0;
memset(s,0,sizeof(s));
n=1;
int now=0;
for(int i=L-1;i>=0;i--){
s[n-1]+=(str[i]-'0')*pow_10[now];
now++;
if(now==BASEL){
now=0;
n++;
}
}
}
void operator = (int b){
memset(s,0,sizeof(s));
n=1;
s[0]=b;
while(s[n-1]>=BASE){
s[n]=s[n-1]/BASE;
s[n-1]%=BASE;
n++;
}
}
void operator += (const HPint &b){
n=max(n,b.n)+1;
for(int i=0;i<n;i++){
s[i]+=b.s[i];
s[i+1]+=s[i]/BASE;
s[i]%=BASE;
}
while(n>1&&s[n-1]==0) n--;
}
void operator += (int b){
s[0]+=b;
for(int i=0;i<n||s[i];i++){
s[i+1]+=s[i]/BASE;
s[i]%=BASE;
if(i+1>n) n=i+1;
}
while(n>1&&s[n-1]==0) n--;
}
void operator -= (const HPint &b){
for(int i=0;i<n;i++){
s[i]-=b.s[i];
while(s[i]<0) s[i+1]--,s[i]+=BASE;
}
while(n>1&&s[n-1]==0) n--;
}
void operator *= (const HPint &b){
static int c[SIZEL];
memset(c,0,sizeof(c));
for(int i=0;i<n;i++){
for(int j=0;j<b.n;j++){
c[i+j]+=s[i]*b.s[j];
c[i+j+1]+=c[i+j]/BASE;
c[i+j]%=BASE;
}
}
n+=b.n;
for(int i=0;i<n||c[i];i++){
c[i+1]+=c[i]/BASE;
c[i]%=BASE;
if(i+1>n) n=i+1;
}
while(n>1&&c[n-1]==0) n--;
memcpy(s,c,sizeof(s));
}
void operator *= (int b){
for(int i=0;i<n;i++) s[i]*=b;
for(int i=0;i<n||s[i];i++){
s[i+1]+=s[i]/BASE;
s[i]%=BASE;
if(i+1>n) n=i+1;
}
while(n>1&&s[n-1]==0) n--;
}
void operator /= (int b){//要求
for(int i=n-1;i>=0;i--){
if(i>0) s[i-1]+=(s[i]%b)*BASE;
s[i]/=b;
}
while(n>1&&s[n-1]==0) n--;
}
};
//本题专用函数......
int operator - (HPint a,const HPint &b){
a-=b;
return a.s[0];
}
void print(const HPint &a){a.print();}
template<typename T> T quickpow(T a,int n){
T ans;ans=1;
while(n){
if(n&1) ans*=a;
a*=a;
n>>=1;
}
return ans;
}
template<typename T> T quickpow(T a,const HPint &n){
T ans;ans=1;
for(int i=0;i<n.n;i++){
ans*=quickpow(a,n.s[i]);
a=quickpow(a,BASE);
}
return ans;
}
//A(x+t)=B(x)
//a的递推式:a[0]=1,a[i]=(1234a[i-1]+5678)%3389
class Matrix{
public:
int n,m;
int s[2][2];
Matrix(){n=m=0;memset(s,0,sizeof(s));}
void operator = (int x){
n=m=2;
memset(s,0,sizeof(s));
for(int i=0;i<2;i++) s[i][i]=x;
}
void operator *= (const Matrix &b){
static int c[2][2];
for(int i=0;i<n;i++){
for(int j=0;j<b.m;j++){
c[i][j]=0;
for(int k=0;k<m;k++){
c[i][j]+=s[i][k]*b.s[k][j]%3389;
c[i][j]%=3389;
}
}
}
m=b.m;
memcpy(s,c,sizeof(s));
}
};
Matrix operator * (Matrix a,const Matrix &b){
a*=b;
return a;
}
HPint N,M;
int D,T;//N-M=D
int A[10]={0};
HPint calc_C(int k){//C(M+k,k)
HPint now=M;
HPint ans;ans=1;
for(int i=0;i<k;i++){
now+=1;
ans*=now;
}
int p=1;
for(int i=1;i<=k;i++) p*=i;
ans/=p;
//cout<<k<<" "<<p<<" ";ans.print();cout<<endl;
return ans;
}
void prepare_A(void){
Matrix ori,step;
ori.n=2,ori.m=1;
ori.s[0][0]=1;ori.s[1][0]=1;
step.n=step.m=2;
step.s[0][0]=1234,step.s[0][1]=5678%3389;
step.s[1][0]=0,step.s[1][1]=1;
Matrix sp_step=quickpow(step,M);
for(int i=0;i<=D;i++){
Matrix now=sp_step*ori;
A[i]=now.s[0][0];
sp_step=sp_step*step;
}
}
void work(void){
HPint ans;ans=0;
for(int i=0;i<=D;i++){
//现在计算多项式a中M+i次项对答案的影响
//这一项是:A[i]*(x+t)^(M+i)
//=A[i]*(x^M)*(t^i)*C(M+i,i)
HPint now;now=A[i];
for(int k=0;k<i;k++) now*=T;
now*=calc_C(i);
ans+=now;
}
ans.print();
printf("\n");
}
char str[3010]={0};
void read(void){
scanf("%s",str);
N=str;
scanf("%d",&T);
scanf("%s",str);
M=str;
D=N-M;
}
int main(){
freopen("cqoi15_polynomial.in","r",stdin);
freopen("cqoi15_polynomial.out","w",stdout);
read();
prepare_A();
work();
return 0;
}