ProjectEuler654

我，ycl:BM是什么早就忘了！

毕老爷:那你们可以做一做这道题练练BM板子啊。

传送门

 1 //Achen 2 #include<bits/stdc  .h> 3 #define For(i,a,b) for(int i=(a);i<=(b);i  ) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=1e5 7,p=1e9 7; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 int n,m;11 LL f[15007][5007];12 13 template<typename T> void read(T &x) {14     char ch=getchar(); T f=1; x=0;15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16     if(ch=='-') f=-1,ch=getchar();17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10 ch-'0'; x*=f;18 }19 20 int main() {21     freopen("1.in","r",stdin);22     //freopen("biao.in","w",stdout);23     read(m); read(n);24     For(i,1,m) f[1][i]=1;25     For(i,1,n) {26         if(i>1) For(j,1,m) f[i][j]=f[i-1][m-j];27         For(j,1,m) f[i][j]=(f[i][j] f[i][j-1])%p;28     }29     printf("%lld\n",f[14555][m]);30     //printf("%d\n",n);31     //For(i,1,n) printf("%lld ",f[i][m]);32     //printf("%lld\n",f[n][m]);33     Formylove;34 }

n^2暴力

//Achen#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<vector>#include<cstdio>#include<queue>#include<cmath>#include<set>#include<map>#define Formylove return 0#define For(i,a,b) for(int i=(a);i<=(b);i  )#define Rep(i,a,b) for(int i=(a);i>=(b);i--)const int N=15007,p=1e9 7;typedef long long LL;typedef double db;using namespace std;int n,cnt,fail[N];vector<LL>f[N];LL a[N],delta[N];template<typename T>void read(T &x)  {    char ch=getchar(); x=0; T f=1;    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();    if(ch=='-') f=-1,ch=getchar();    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10 ch-'0'; x*=f;}LL ksm(LL a,LL b) {    LL rs=1,bs=a%p;    while(b) {        if(b&1) rs=rs*bs%p;        bs=bs*bs%p;        b>>=1;    }    return rs;}#define ANSint main() {#ifdef ANS    freopen("biao.in","r",stdin);    freopen("shizi.out","w",stdout);#endif    read(n);    For(i,1,n) read(a[i]);    For(i,1,n) {        LL tp=0; int up=f[cnt].size();        For(j,0,up-1) tp=(tp f[cnt][j]*a[i-j-1]%p)%p;        if(tp==a[i]) continue;        delta[i]=(a[i]-tp p)%p;        fail[cnt]=i;          cnt;        if(cnt==1) {            f[cnt].resize(i);            continue;        }        LL mul=delta[i]*ksm(delta[fail[cnt-2]],p-2)%p,fmul=(p-mul)%p;        f[cnt].resize(i-fail[cnt-2]-1);        f[cnt].push_back(mul);        up=f[cnt-2].size();        For(j,0,up-1) f[cnt].push_back(fmul*f[cnt-2][j]%p);        up=f[cnt-1].size();        if(f[cnt].size()<f[cnt-1].size()) f[cnt].resize(up);        For(j,0,up-1) f[cnt][j]=(f[cnt][j] f[cnt-1][j])%p;     }    int up=f[cnt].size();    printf("%d\n",up);    For(i,0,up-1) printf("%lld ",f[cnt][i]);    Formylove;}

BM出递推

 1 //Achen 2 #include<bits/stdc  .h> 3 #define For(i,a,b) for(int i=(a);i<=(b);i  ) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=1e5 7,p=1e9 7; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 int cnt;11 LL A[N],f[N],n;12 13 template<typename T> void read(T &x) {14     char ch=getchar(); T f=1; x=0;15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16     if(ch=='-') f=-1,ch=getchar();17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10 ch-'0'; x*=f;18 }19 20 LL rs[N],bs[N],tp[N];21 void cheng(LL a[],LL b[]) {22     For(i,0,cnt*2) tp[i]=0;23     For(i,0,cnt-1) For(j,0,cnt-1)24         (tp[i j] =a[i]*b[j])%=p;25     Rep(i,cnt*2-2,cnt) if(tp[i])26         For(j,0,cnt-1) 27             (tp[i-j-1] =A[j]*tp[i]%p)%=p;28     For(i,0,cnt-1) a[i]=tp[i];29 }30 31 void ksm(LL b) {32     while(b) {33         if(b&1) cheng(rs,bs);34         cheng(bs,bs);35         b>>=1;36     }37 }38 39 int main() {40     freopen("shizi.out","r",stdin);41     //freopen("shizi.out","w",stdout);42     read(cnt);43     For(i,0,cnt-1) read(A[i]);44     read(n);45     rs[0]=1; bs[1]=1; ksm(n-1);46     For(i,1,cnt) read(f[i]);47     LL ans=0;48     For(i,0,cnt-1) ans=(ans f[i 1]*rs[i]%p)%p;49     printf("%lld\n",ans);50     Formylove;51 }

多项式取模

 

来源：http://www.icode9.com/content-4-138101.html