哎呀大水題。。我寫了一個(gè)多小時(shí)。。好沒救啊。。

數(shù)論板子X合一？

注意: 本文中變量名稱區(qū)分大小寫。

題意: 給一個(gè)\(n\)階遞推序列\(f_k=\prod^{n}_{i=1} f_{k-i}^{b_i}\mod P\)其中\(P=998244353\), 輸入\(b_1,b_2,...,b_n\)以及已知\(f_1,f_2,...,f_{n-1}=1\), 再給定一個(gè)數(shù)\(m\)和第\(m\)項(xiàng)的值\(f_m\), 求出一個(gè)合法的\(f_n\)值使得按照這個(gè)值遞推出來(lái)的序列滿足第\(m\)項(xiàng)的值為給定的\(f_m\).

題解: 首先一個(gè)顯然的結(jié)論是\(f_m\)可以表示成\(\prod^{n}_{i=1} f_i^{a_i}\), 而且由于\(i=1,2,...,n-1\)時(shí)\(f_i\)的任何次冪都為\(1\), 因此就是\(f_m=f_n^{a}\). 令\(A(m)\)為\(f_m\)內(nèi)\(f_n\)的次數(shù)，則有\(A[1..n]=[0,0,0,0,...,0,1]\), \(A_m=\sum^{n-1}_{i=1} A(m-i)b_i (m>n)\), 即\(A\)數(shù)組滿足一個(gè)常系數(shù)線性遞推序列。因此可以用矩陣乘法在\(O(n^3\log m)\)的時(shí)間內(nèi)求出\(A(m)\). 注意因?yàn)槭侵笖?shù)的運(yùn)算(\((a^n)^m=a^{nm}\)), 根據(jù)費(fèi)馬小定理，這個(gè)指數(shù)應(yīng)該模\(\phi(P)=P-1\)而不是\(P\) (\((a^n)^m\mod P=a^{nm\mod (P-1)}\mod P\))

求出來(lái)\(a=A(m)\)之后這題就變成了，\(f_m=f_n^a\mod P\), 已知\(f_m, a\), 求出一組合法的\(f_n\).

根據(jù)常識(shí)，\(998244353\)有原根\(3\), 我們下文令\(G=3\) (實(shí)際上任何一個(gè)原根均可). 設(shè)\(f_m=G^p, f_n=G^q\), 則有\(G^p\equiv (G^q)^a (\mod P)\), \(p\equiv qa(\mod P-1)\), 然后用BSGS求離散對(duì)數(shù)\(p\), exgcd解出\(q\)就可以了啊……

時(shí)間復(fù)雜度\(O(\sqrt P\log P+n^3\log P)\)

坑: 注意解同余方程的時(shí)候那個(gè)\(P\)的系數(shù)不要設(shè)成負(fù)的。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<map> #define llong long long using namespace std;const int N = 100; const int G = 3; const int P = 998244353; llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } struct Matrix {llong a[N+3][N+3]; int sz1,sz2,sz;void init() {for(int i=1; i<=sz1; i++) for(int j=1; j<=sz2; j++) a[i][j] = 0ll;}Matrix() {}Matrix(int _sz) {sz = sz1 = sz2 = _sz; init();}Matrix(int _sz1,int _sz2) {sz1 = _sz1,sz2 = _sz2; init();}void uinit(int _sz) {sz = sz1 = sz2 = _sz; for(int i=1; i<=sz; i++) for(int j=1; j<=sz; j++) a[i][j] = (i==j)?1:0;}void output() {for(int i=1; i<=sz1; i++) {for(int j=1; j<=sz2; j++) printf("%lld ",a[i][j]); puts("");}} }; Matrix operator *(Matrix x,Matrix y) {Matrix ret = Matrix(x.sz1,y.sz2);for(int i=1; i<=x.sz1; i++){for(int j=1; j<=x.sz2; j++){for(int k=1; k<=y.sz2; k++){ret.a[i][j] = (ret.a[i][j]+x.a[i][k]*y.a[k][j])%(P-1ll);}}}return ret; } Matrix mquickpow(Matrix x,llong y) {Matrix cur = x,ret; ret.uinit(x.sz);for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur;}cur = cur*cur;}return ret; } namespace BSGS {const int B = 31595;map<llong,int> mp;void init(){llong bs = quickpow(G,B); llong j = 1ll;for(int i=0; i<=P; i+=B,j=(j*bs)%P){mp[j] = i;}}llong Logarithm(llong x){llong j = 1ll;for(int i=0; i<=B; i++,j=(j*G)%P){llong tmp = x*j%P;if(mp.count(tmp)){llong ret = (mp[tmp]-i+(P-1))%(P-1);return ret;}}return P-1;} } Matrix mA,mB,mC; llong a[N+3],b[N+3]; int n; llong m,p,q,lq,lx;llong gcd(llong x,llong y) {return y==0 ? x : gcd(y,x%y);} void exgcd(llong _a,llong _b,llong &_x,llong &_y) {if(_b==0ll) {_x = 1ll,_y = 0ll; return;}exgcd(_b,_a%_b,_x,_y);llong tmp = _x; _x = _y; _y = tmp-(_a/_b)*_y; } llong CongruenceEquation(llong _a,llong _b,llong mod) {llong g = gcd(_a,mod),x,y;exgcd(_a/g,mod/g,x,y);return (x*(_b/g)%mod+mod)%mod; }int main() {BSGS::init();scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%I64d",&b[i]);scanf("%I64d",&m);mA = Matrix(1,n); mA.a[1][1] = 1ll;mB = Matrix(n); for(int i=1; i<n; i++) mB.a[i][i+1] = 1ll; for(int i=1; i<=n; i++) mB.a[i][1] = b[i];mC = mA*mquickpow(mB,m-n); p = mC.a[1][1]; scanf("%I64d",&q);lq = BSGS::Logarithm(q);if(lq%gcd(P-1,p)!=0) {printf("-1\n"); return 0;}lx = CongruenceEquation(p,lq,P-1);llong ans = quickpow(G,lx);printf("%I64d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1106F Lunar New Year and a Recursive Sequence (线性代数、线性递推、数论、BSGS、扩展欧几里得算法)...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。