「CSA49」Bunny on Number Line

題目大意：有一個人從0開始走，每次可以向前走一步或者回到1，那么會產生一個位置序列，其中給出 \(k\) 個位置是好的。定義一個位置序列是好的，當前僅當其有恰好 \(n\) 個位置是好的，且最后一個位置是好的，相鄰兩個好的位置距離不超過 \(m\) ，求本質不同的好的序列的長度之和。兩個序列本質不同當且僅當存在一個位置滿足在其中一個序列中上的位置是好的，另外一個不是。

解題思路：問題轉換一下，將好的位置看作 1 ，其它的位置看作 0，組成一個01字符串。那么每次往后走到一個好的位置，相當于往后接一個以1結尾的前綴，然后求這樣所得的所有不同的字符串的長度之和。實際上所有1和0都是一樣的，區分字符串只有每個1前面的0的數量不同。于是可以重新定義字符 \(b_i =a_i-a_{i-1}\) 。問題轉化為求出所有由 \(b\) 組成的合法的不同字符串的長度之和，事實上求長度之和要用到方案數，而方案數會求了長度之和自然就能求了，所以下面就講方案數怎么求。

考慮一個樸素的做法，令 \(dp(i,j)\) 表示當前長度為 \(i\) 的字符串末尾的字符是 \(b_j\) 的方案數，考慮 \(dp(i,j)\) 向后轉移本質上是原串在某一時刻向后加了一個以 \(b_j\) 結尾的前綴，然后轉移到這個前綴后面的那個字符。且這個前綴還必須與當前確定的串的后綴匹配，不然就會產生不合法的方案數。分析一下會發現這是一個kmp不斷跳失配指針的過程，直接跳轉移即可。不過還有幾個情況要討論一下，如果出現之前長度較長的前綴已經能轉移到某個 \(c\) ，當前也要轉移到 \(c\) ，此時會發現轉移后的串本質是一樣的，只是 \(j\) 的大小不一樣，而由于長的串跳失配指針一定能包含短的串，所以只轉移到較長的那個即可。另外 \(b_1\) 是一個通配符可以匹配 \([a_1,m]\) 之間的所有字符，因為其可以不斷跳若干次1再走到第一個好的位置，所以要對與 \(b_1\) 的匹配加以特判。

然后這個轉移求完之后同理可以利用方案數來求總長度，只需要對每個字符加權計算即可，\(b_1\) 的權是 \(\sum_{i=a_1}^mi\) ，最后矩陣快速冪優化一下這個轉移即可，總復雜度 \(O(k^3logn)\) ，用 BM 可以做到 \(O(k^2)\) 。

code

/*program by mangoyang*/ #include<bits/stdc++.h> #define inf (0x7f7f7f7f) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) typedef long long ll; using namespace std; template <class T> inline void read(T & x){int ch = 0, f = 0; x = 0;for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;if(f) x = -x; }#define int ll #define fi first #define se secondconst int N = 105, mod = 1e9+7;map<int, int> mp; int nxt[N], a[N], b[N], n, m, k, ans; inline void add(int &x, int y){ x = x + y >= mod ? x + y - mod : x + y; } inline void del(int &x, int y){ x = x - y < 0 ? x - y + mod : x - y; }struct Matrix{pair<int, int> a[N][N];inline Matrix(){ memset(a, 0, sizeof(a)); }inline Matrix operator * (const Matrix &B) const{Matrix ans;for(int i = 1; i <= k; i++)for(int j = 1; j <= k; j++)for(int p = 1; p <= k; p++){add(ans.a[i][j].fi, a[i][p].fi * B.a[p][j].fi % mod);add(ans.a[i][j].se, a[i][p].fi * B.a[p][j].se % mod);add(ans.a[i][j].se, a[i][p].se * B.a[p][j].fi % mod);}return ans;} }A, B;inline Matrix Pow(Matrix A, int b){Matrix ans = A; b--;for(; b; b >>= 1, A = A * A)if(b & 1) ans = ans * A;return ans; }inline int same(int x, int y){ return y == 1 ? (b[x] >= a[1]) : (b[x] == b[y]); } signed main(){read(k), read(m), read(n), nxt[0] = -1;for(int i = 1; i <= k; i++) read(a[i]), b[i] = a[i] - a[i-1];for(int i = 2, j = 0; i <= k; nxt[i++] = ++j)while(~j && !same(i, j + 1)) j = nxt[j];int tot = (m - a[1] + 1), sum = tot * (a[1] + m) / 2 % mod;for(int i = 1; i <= k; i++){mp.clear();for(int p = i; p; p = nxt[p]) if(!mp[b[p+1]]){A.a[p+1][i] = make_pair(1ll, b[p+1]);if(b[p+1] >= a[1])del(A.a[1][i].fi, 1), del(A.a[1][i].se, b[p+1]);mp[b[p+1]] = 1;}add(A.a[1][i].fi, tot), add(A.a[1][i].se, sum);}if(n == 1) return cout << sum, 0;B.a[1][1] = make_pair(tot, sum), A = Pow(A, n - 1) * B;for(int i = 1; i <= k; i++) add(ans, A.a[i][1].se);cout << ans; }

轉載于:https://www.cnblogs.com/mangoyang/p/10407087.html

總結

以上是生活随笔為你收集整理的「CSA49」Bunny on Number Line的全部內容，希望文章能夠幫你解決所遇到的問題。

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