Java教程

[loj138]类欧几里得算法

本文主要是介绍[loj138]类欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

模板题

定义$\lfloor x\rfloor$表示小于等于$x$的最大整数,$\lceil x\rceil$表示大于等于$x$的最小整数

不难发现,若$a\in Z^{+}$且$b,x\in Z$,则$ax\le b\iff x\le \lfloor\frac{b}{a}\rfloor$、$ax\ge b\iff x\ge \lfloor\frac{b-1}{a}\rfloor+1$

通过拉格朗日插值法,预处理出$S_{k}(n)=\sum_{i=0}^{n}i^{k}$(定义$0^{0}=1$)关于$n$的$k+1$次多项式,并记其中的$i$次项系数为$S_{k}[i]$,即有$S_{k}(n)=\sum_{i=0}^{k+1}S_{k}[i]\cdot n^{i}$

记$F_{k_{1},k_{2}}(n,a,b,c)=\sum_{x=0}^{n}x^{k_{1}}\lfloor\frac{ax+b}{c}\rfloor^{k_{2}}$,问题即求该式$F_{k_{1},k_{2}}(n,a,b,c)$

对其分类讨论:

1.若$n<0$,那么原式即为0

2.若$a\not\in [0,c)$,不妨假设$a=ic+a'$(其中$i\in Z$且$a'\in [0,c)$​),那么原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}(\lfloor\frac{a'x+b}{c}\rfloor+ix)^{k_{2}}\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{k=0}^{k_{2}}{k_{2}\choose k}\lfloor\frac{a'x+b}{c}\rfloor^{k}(ix)^{k2-k}\\
&=\sum_{k=0}^{k_{2}}{k2\choose k}i^{k_{2}-k}F_{k_{1}+k_{2}-k,k}(n,a',b,c)\end{array}
$$
3.若$b\not\in [0,c)$,不妨假设$b=ic+b'$(其中$i\in Z$且$b'\in [0,c)$),那么原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}(\lfloor\frac{ax+b'}{c}\rfloor+i)^{k_{2}}\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{k=0}^{k_{2}}{k_{2}\choose k}\lfloor\frac{ax+b'}{c}\rfloor^{k}i^{k2-k}\\
&=\sum_{k=0}^{k_{2}}{k2\choose k}i^{k_{2}-k}F_{k_{1},k}(n,a,b',c)\end{array}
$$
4.不为以上几种情况,先处理$k_{2}=0$的部分,即$F_{k_{1},0}(n,a,b,c)=\sum_{x=0}^{n}x^{k_{1}}=S_{k_{1}}(n)$

接下来,若$a=0$则其余部分均为0,否则原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{i=0}^{\lfloor\frac{ax+b}{c}\rfloor-1}\left((i+1)^{k_{2}}-i^{k_{2}}\right)\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{i=0}^{\lfloor\frac{ax+b}{c}\rfloor-1}\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}i^{k}\\
&=\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{i=0}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\sum_{x=\lfloor\frac{ic+c-b-1}{a}\rfloor+1}^{n}x^{k_{1}}\\
&=\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{i=0}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\left(S_{k_{1}}(n)-S_{k_{1}}(\lfloor\frac{ic+c-b-1}{a}\rfloor)\right)\\
&=C-\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{i=0}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\sum_{k'=0}^{k_{1}+1}S_{k_{1}}[k']\cdot \lfloor\frac{ic+c-b-1}{a}\rfloor^{k'}\\
&=C-\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{k'=0}^{k_{1}+1}S_{k_{1}}[k']\cdot F_{k,k'}(\lfloor\frac{an+b}{c}\rfloor-1,c,c-b-1,a)\end{array}
$$
其中$k_{2}>0$,$C$为$S_{k_{1}}(n)$对应的部分,即
$$
C=\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}S_{k}(\lfloor\frac{an+b}{c}\rfloor-1)S_{k_{1}}(n)
$$
考虑递归计算,即对于状态$(n,a,b,c)$求出所有$k_{1},k_{2}\in N^{*}$的$F_{k_{1},k_{2}}(n,a,b,c)$,注意到转移的$k_{1}+k_{2}$单调不增,因此只需要考虑$k_{1}+k_{2}\le K=10$的状态即可

由此,递归状态内的计算复杂度为$o(K^{4})$,而状态中的$a$和$c$即为辗转相除,即递归层数为$o(\log n)$

综上,时间复杂度为$o(tK^{4}\log n)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 15
 4 #define K 10
 5 #define mod 1000000007
 6 #define ll long long
 7 struct Data{
 8     int a[N][N];
 9     Data(){
10         memset(a,0,sizeof(a));
11     }
12 };
13 int t,n,a,b,c,k1,k2,inv[N],C[N][N],mi[N],g[N],S[N][N];
14 void init(){
15     inv[0]=inv[1]=1;
16     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
17     for(int i=0;i<N;i++){
18         C[i][0]=C[i][i]=1;
19         for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
20     }
21     for(int i=0;i<N;i++)mi[i]=1;
22     for(int i=0;i<=K;i++){
23         int s=0;
24         for(int j=0;j<=i+1;j++){
25             s=(s+mi[j])%mod;
26             int sum=s;
27             memset(g,0,sizeof(g));
28             g[0]=1;
29             for(int k=0;k<=i+1;k++)
30                 if (j!=k){
31                     sum=(ll)sum*inv[abs(j-k)]%mod;
32                     if (j<k)sum=mod-sum;
33                     for(int l=i+1;l;l--)g[l]=(g[l-1]-(ll)g[l]*k%mod+mod)%mod;
34                     g[0]=mod-(ll)g[0]*k%mod;
35                 }
36             for(int k=0;k<=i+1;k++)S[i][k]=(S[i][k]+(ll)sum*g[k])%mod;
37         }
38         for(int j=0;j<N;j++)mi[j]=(ll)mi[j]*j%mod;
39     }
40 }
41 int get_sum(int k,int n){
42     int s=1,ans=0;
43     for(int i=0;i<=k+1;i++){
44         ans=(ans+(ll)S[k][i]*s)%mod;
45         s=(ll)s*n%mod;
46     }
47     return ans;
48 }
49 Data dfs(int n,int a,int b,int c){
50     Data ans;
51     if (n<0)return ans;
52     if (a>=c){
53         Data s=dfs(n,a%c,b,c);
54         mi[0]=1;
55         for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*(a/c)%mod;
56         for(int k1=0;k1<=K;k1++)
57             for(int k2=0;k1+k2<=K;k2++)
58                 for(int k=0;k<=k2;k++)ans.a[k1][k2]=(ans.a[k1][k2]+(ll)C[k2][k]*mi[k2-k]%mod*s.a[k1+k2-k][k])%mod;
59         return ans;
60     }
61     if (b>=c){
62         Data s=dfs(n,a,b%c,c);
63         mi[0]=1;
64         for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*(b/c)%mod;
65         for(int k1=0;k1<=K;k1++)
66             for(int k2=0;k1+k2<=K;k2++)
67                 for(int k=0;k<=k2;k++)ans.a[k1][k2]=(ans.a[k1][k2]+(ll)C[k2][k]*mi[k2-k]%mod*s.a[k1][k])%mod;
68         return ans;
69     }
70     for(int k1=0;k1<=K;k1++)ans.a[k1][0]=get_sum(k1,n);
71     if (!a)return ans;
72     int nn=((ll)a*n+b)/c;
73     Data s=dfs(nn-1,c,c-b-1,a);
74     for(int k1=0;k1<=K;k1++)
75         for(int k2=1;k1+k2<=K;k2++)
76             for(int k=0;k<k2;k++){
77                 int sum=0;
78                 for(int kk=0;kk<=k1+1;kk++)sum=(sum+(ll)S[k1][kk]*s.a[k][kk])%mod;
79                 sum=((ll)get_sum(k,nn-1)*ans.a[k1][0]-sum+mod)%mod;
80                 sum=(ll)sum*C[k2][k]%mod;
81                 ans.a[k1][k2]=(ans.a[k1][k2]+sum)%mod;
82             }
83     return ans;
84 }
85 int main(){
86     init();
87     scanf("%d",&t);
88     while (t--){
89         scanf("%d%d%d%d%d%d",&n,&a,&b,&c,&k1,&k2);
90         printf("%d\n",dfs(n,a,b,c).a[k1][k2]);
91     }
92     return 0;
93 }
View Code

 

这篇关于[loj138]类欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!