目錄

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

定義遞推數列 f：

（1）f[1] = f[2] = ... f[k-1] = 1，f[k] 是一個未知量。
（2）f[i] = (f[i-1]^b[1]) * (f[i-2]^b[2]) * ... *(f[i-k]^b[k]) mod 998244353。

其中 k 和 b[1...k] 是給定的常量。現在已知數列的第 n 項 f[n] = m，求 f[k]。

input
第一行一個整數 k (1 <= k <= 100)。
接下來一行 k 個整數 b1, b2, ..., bk (1 <= bi < 998244353)。
接下來一行兩個整數 n, m (k < n <= 10^9, 1 <= m < 998244353)。

output
輸出 fk 的值。若不存在，輸出 -1。若多解，輸出任意一個。

sample input
3
2 3 5
4 16
sample output
4

@solution@

首先，我們想要在 fk 與 fn 之間建立關系。

不難猜想到 fn = fk^x，同時這也暗示我們可以將 1 看成 fk^0。

這樣的話原本是非線性遞推式，就可以變成指數的線性遞推式。可以用矩陣快速冪解出 x 的值。

現在，我們已知 fk^x = fn = m mod 998244353，想要解出 fk 的值。

這是一個經典的數論問題：高次剩余。它有一些復雜的方法，但是對于這個特殊的模數，我們還有一種較為簡潔的方法：利用原根。

根據原根的性質，我們可以將任意一個數寫成原根的冪的形式。這樣上面的式子就會變為 g^(px) = g^q mod 998244353。

通過 BSGS 可以快速解出 q 的值。這樣我們只需要根據指數相等列出同余方程用 exgcd 解出 p 的值就可以解決此題了。

@accepted code@

#include<cstdio> #include<vector> #include<cmath> using namespace std; const int MAXK = 100 + 5; const int MOD = 998244353; const int MODPW = MOD - 1; const int HASHSIZE = 1000037; struct node{int ind, key;node(int _i=0, int _k=0):ind(_i), key(_k){} }; vector<node>h[HASHSIZE]; void hash_insert(int n, int x) {h[x%HASHSIZE].push_back(node(n, x)); } int hash_search(int x) {int y = x%HASHSIZE;for(int i=0;i<h[y].size();i++)if( h[y][i].key == x ) return h[y][i].ind;;return -1; } void hash_clear() {for(int i=0;i<HASHSIZE;i++)h[i].clear(); } struct matrix{int m[MAXK][MAXK];int r, c; }A, B; matrix operator * (matrix A, matrix B) {matrix C; C.r = A.r, C.c = B.c;for(int i=0;i<C.r;i++)for(int j=0;j<C.c;j++) {C.m[i][j] = 0;for(int k=0;k<A.c;k++)C.m[i][j] = (C.m[i][j] + 1LL*A.m[i][k]*B.m[k][j]%MODPW)%MODPW;}return C; } matrix mpow(matrix A, int p) {matrix ret; ret.r = ret.c = A.r;for(int i=0;i<ret.r;i++)for(int j=0;j<ret.c;j++)ret.m[i][j] = (i == j);while( p ) {if( p & 1 ) ret = ret*A;A = A*A;p >>= 1;}return ret; } int solve1() {int k, n; scanf("%d", &k);for(int i=0;i<k;i++) scanf("%d", &A.m[k-1][k-i-1]);A.r = A.c = B.r = k; B.c = 1;for(int i=0;i<k;i++) B.m[i][0] = 0;B.m[k-1][0] = 1;for(int i=0;i<k-1;i++)for(int j=0;j<k;j++)A.m[i][j] = 0;for(int i=0;i<k-1;i++) A.m[i][i+1] = 1;scanf("%d", &n); B = mpow(A, n-k)*B;return B.m[k-1][0]; } int pow_mod(int b, int p, int mod) {int ret = 1;while( p ) {if( p & 1 ) ret = 1LL*ret*b%mod;b = 1LL*b*b%mod;p >>= 1;}return ret; } int BSGS(int a, int b) {hash_clear();int m = int(ceil(sqrt(MOD))), tmp = 1, tmp2;for(int i=0;i<=m;i++) {if( i == m ) tmp2 = tmp;hash_insert(i, 1LL*tmp*b%MOD);tmp = 1LL*tmp*a%MOD;}tmp = tmp2;for(int i=1;i<=m;i++) {if( hash_search(tmp) != -1 ) {return i*m - hash_search(tmp);}tmp = 1LL*tmp*tmp2%MOD;} } typedef long long ll; ll exgcd(ll a, ll b, ll &x, ll &y) {if( b == 0 ) {x = 1, y = 0;return a;}else {ll x1, y1;ll d = exgcd(b, a%b, x1, y1);x = y1;y = x1 - a/b*y1;return d;} } int solve2(int a, int p) {int b = BSGS(3, a);ll x, y, d = exgcd(p, MODPW, x, y);if( b % d ) return -1;else {x = (1LL*x*b/d%MODPW + MODPW)%MODPW;return pow_mod(3, x, MOD);} } int main() {int m, p = solve1(); scanf("%d", &m);printf("%d\n", solve2(m, p)); }

@details@

WC2019 講了“簡單”數論，所以就記住了這一算法，然后沒想到這一次就用到了。

然而我并沒有寫過 BSGS，比賽的時候現學的（又是這樣嘛……上一次 manacher 也是比賽的時候現學的……）
所以打 CF 還是有用的 2333。

靠著 CF 官方評測系統出鍋，續了 40 min，終于把這道題寫出來了。
人生第一次 AK。感謝 CF 的評測系統。
只不過 unrated 有點兒可惜 www。

本次比賽好像就這道題有點兒意思（因為是沒有寫過的新知識）。
A：大模擬
B：英語閱讀理解 + 大模擬
C：常見貪心結論
D：一個關于圖論的簡單貪心
E：英語閱讀理解 + 簡單 dp

轉載于:https://www.cnblogs.com/Tiw-Air-OAO/p/10344467.html

總結

以上是生活随笔為你收集整理的@codeforces - 1106F@ Lunar New Year and a Recursive Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。