Loading... 课后练习题 ### 题目描述 #### 原题 小`Y`这两天学习了幂函数，他在老师的课后练习题中看到了这么一个问题：给定正整数$n,k$，求函数$y=x^k-n$的零点个数。小`Y` 一眼就看出了这个问题等价于求方程$x^k=n$的解的个数。可是他觉得这个问题很没意思，于是稍稍修改了一下这个问题：求方程$x^k \equiv n \pmod{x+1}$的解的个数。现在轮到你来解决这个问题了。 #### 简明题意 求如下方程**正整数**解的个数。 $$ x^k \equiv n \pmod{x+1} $$ ### 输入格式 一行，两个正整数$n,k$。 ### 输出格式 共一行，一个整数$ans$表示解的个数。 ### 样例 #### 样例输入#1 ```bash 14 1 ``` #### 样例输出#1 ```bash 3 ``` #### 样例解释#1 解集是$\left\{2,4,14\right\}$。 #### 样例输入#2 ```bash 1919 810 ``` #### 样例输出#2 ```bash 7 ``` ### 数据范围 - 对于$50\%$的数据，$k=1$； - 对于$100\%$的数据，$1 \leq k,n \leq 10^{14}$。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); unsigned long long n,k,ans=0,cnt=0,i=1; cin>>n>>k; if(k&1){ n++; } else{ n--; } for(;i*i<n;i++){ if(!(n%i)){ cnt+=2; } } cnt+=(i*i==n); cout<<cnt-1<<endl; return 0; } ``` ### 题解 $$ \because n \equiv x^k \pmod{x+1}\\ k=2,s.t.x^2\equiv x(x+1)-x\equiv-x\equiv1\pmod{x+1};\\ k=3,s.t.x^3\equiv x^2x\equiv x\pmod{x+1}\\ \therefore \begin{cases} n\equiv x\pmod{x+1}(k\equiv1\pmod{2})\\ n\equiv 1\pmod{x+1}(k\equiv0\pmod{2}) \end{cases}\\ \therefore \begin{cases} n+1\equiv 0\pmod{x+1}(k\equiv1\pmod{2})\\ n-1\equiv 0\pmod{x+1}(k\equiv0\pmod{2}) \end{cases} $$ 分情况考虑统计因数个数即可。 ## 拼图 ### 题目描述 #### 原题面 小`Y`得到了一个新的拼图玩具，玩具由一个$4 \times n$的木板，无数块$1\times 4$的拼图和无数块$2\times 2$的拼图组成。 显然要把这个木板拼完很简单，但是小`Y`想知道，拼完这个木板一共有多少种不同的方案。 方案数对$10^9+7$取模。 #### 简明题意 求用无数块大小为$2 \times 2$的木板和无数块大小为$1 \times 4$的木板拼成一块大小为$n \times 4$的木板的方案数。 ### 输入格式 共一行，一个正整数$n$。 ### 输出格式 共一行，一个整数$ans$表示示方案数对$10^9+7$取模的结果。 ### 样例 #### 样例输入#1 ```bash 4 ``` #### 样例输出#1 ```bash 9 ``` #### 样例输入#2 ```bash 1919810 ``` #### 样例输出#2 ```bash 984599383 ``` ### 数据范围 - 对于$20\%$的数据，$4 \leq n \leq 10$； - 对于$50\%$的数据，$4 \leq n\leq 10^6$； - 对于$100\%$的数据，$4 \leq n\leq 10^{18}$。 <div class="tip inlineBlock error"> 该题目由于原始代码和题解都没考虑一些情况，下面的错误题这里编辑标签内容解和错误代码仅供娱乐。 </div> ### 错误题解 设$f_x$为拼$4\times x$的模板的方案数。 根据画画可知递推式$f_x=f_{x-1}+f_{x-2}+f_{x-4}\times 4$。 显然构造矩阵并使用矩阵快速幂。 $$ \begin{bmatrix}f_x\\f_{x-1}\\f_{x-2}\\f_{x-3}\end{bmatrix}\times\begin{bmatrix}1&1&0&4\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{bmatrix}=\begin{bmatrix}f_{x+1}\\f_x\\f_{x-1}\\f_{x-2}\end{bmatrix} $$ #### 代码 ```cpp #include <bits/stdc++.h> using namespace std; const unsigned int MOD=1000000007; struct Matrix{ unsigned long long a[5][2]; Matrix(){ memset(a,0,sizeof(a)); } Matrix operator*(const Matrix &b )const{ Matrix res; for(int i=1;i<=4;i++ ) for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%MOD; return res; } }ans,base; void qpow(unsigned long long b) { while (b){ if(b&1) ans=ans*base; base=base*base; b >>= 1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); unsigned long long n; cin>>n; base.a[1][3]=base.a[1][4]=base.a[2][5]=base.a[3][6]=base.a[4][7]=1; base.a[1][8]=4; ans.a[1][9]=ans.a[0][0]=ans.a[2][10]=ans.a[4][11]=1; qpow(n); cout<<ans.a[1][12]%MOD<<endl; return 0; } ``` ### 正确题解（By吴清月） 方法和上面的错误题解是一样的，但是显然情况未考虑完全。 设$f_x$为拼$4\times x$的模板的方案数。 根据画画可知递推式$f_x=f_{x-1}+f_{x-2}+4f_{x-4}+2f_{x-6}+3f_{x-8}+2f_{x-10}+\cdots$。后面系数是$2,3$交替。 则$f_{x-4}=f_{x-5}+f_{x-6}+4f_{x-8}+2f_{x-10}+3f_{x-12}+\cdots$，后面系数是$2,3$交替。 错位相减即可。 下面介绍如何干递推式。括号内的数字是方法数。下面有参考图。 #### $f(x-1)$ - 一个竖直木块。（$1$） #### $f(x-2)$ - 竖着摆放两个方木块。（$1$） #### $4f(x-4)$ - $4$个横木块。（$1$） - 可以两个横木块和两个方木块。（$3$） !> 请注意不要搞重复了。 #### $2f(x-6)$ - $(2\times2+(1\times4)\times2)\times2$。（$2$） #### $3f(x-8)$ - 有两行是两个$1\times4$。还有一行是边上两个$2\times2$中间两个$1\times4$（$3$） 往后同理。 显然构造矩阵并使用矩阵快速幂。 #### 代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int N = 20; ll f[N] = { 0, 1, 2, 3, 9, 16, 35, 65, 143, 281, 590 }; // f[i] = f[i-1] + f[i-2] + 5*f[i-4] - f[i-5] + f[i-6] - f[i-8] struct Mat { ll m[9][24]; int siza, sizb; Mat() { memset( m, 0, sizeof( m ) ); } void clear() { memset( m, 0, sizeof( m ) ); } } A; Mat operator*( Mat a, Mat b ) { Mat ans; for ( int i = 1; i <= a.siza; ++i ) for ( int j = 1; j <= b.sizb; ++j ) for ( int k = 1; k <= a.sizb; ++k ) ans.m[i][j] = ( ans.m[i][j] + 1ll * a.m[i][k] * b.m[k][j] % mod + mod ) % mod; ans.siza = a.siza; ans.sizb = b.sizb; return ans; } ll n; int main() { cin >> n; if ( n <= 8 ) { printf( "%lld\n", f[n] ); return 0; } A.clear(); A.siza = A.sizb = 8; A.m[1][25] = A.m[2][26] = 1; A.m[3][27] = 0; A.m[4][28] = 5; A.m[5][29] = -1; A.m[6][30] = 1; A.m[7][31] = 0; A.m[8][32] = -1; for ( int i = 2; i <= 8; ++i ) A.m[i - 1][i] = 1; Mat F; F.siza = 1; F.sizb = 8; F.m[1][33] = 1; F.m[1][34] = 2; F.m[1][35] = 3; F.m[1][36] = 9; F.m[1][37] = 16; F.m[1][38] = 35; F.m[1][39] = 65; F.m[1][40] = 143; n -= 8; while ( n ) { if ( n & 1 ) F = F * A; A = A * A; n >>= 1; } printf( "%lld\n", F.m[1][41] ); return 0; } ``` ### 正确题解（By钟神） 既然肉眼无法看出递推式。那么暴力搜索前面的结果。然后用`杜教BM`暴力推出递推式。 `BM`推线性递推式，最低阶的复杂度好像是$n^2log_2n$。$n$是输入项数，比高斯消元算快很多。 下面附上`杜教BM`的代码。 ```cpp #include <bits/stdc++.h> using namespace std; #define rep( i, a, n ) for ( int i = a; i < n; i++ ) #define SZ( x ) ( ( long long )( x ).size() ) const long long MOD = 1000000007; long long powmod( long long a, long long b ) { long long res = 1; a %= MOD; assert( b >= 0 ); for ( ; b; b >>= 1 ) { if ( b & 1 ) res = res * a % MOD; a = a * a % MOD; } return res; } long long _, n; namespace linear_seq { const long long N = 10010; long long res[N], base[N], _c[N], _md[N]; vector< long long > Md; void mul( long long* a, long long* b, long long k ) { rep( i, 0, k + k ) _c[i] = 0; rep( i, 0, k ) if ( a[i] ) rep( j, 0, k ) _c[i + j] = ( _c[i + j] + a[i] * b[j] ) % MOD; for ( long long i = k + k - 1; i >= k; i-- ) if ( _c[i] ) rep( j, 0, SZ( Md ) ) _c[i - k + Md[j]] = ( _c[i - k + Md[j]] - _c[i] * _md[Md[j]] ) % MOD; rep( i, 0, k ) a[i] = _c[i]; } long long solve( long long n, vector< long long > a, vector< long long > b ) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+... long long ans = 0, pnt = 0; long long k = SZ( a ); assert( SZ( a ) == SZ( b ) ); rep( i, 0, k ) _md[k - 1 - i] = -a[i]; _md[k] = 1; Md.clear(); rep( i, 0, k ) if ( _md[i] != 0 ) Md.push_back( i ); rep( i, 0, k ) res[i] = base[i] = 0; res[0] = 1; while ( ( 1ll << pnt ) <= n ) pnt++; for ( long long p = pnt; p >= 0; p-- ) { mul( res, res, k ); if ( ( n >> p ) & 1 ) { for ( long long i = k - 1; i >= 0; i-- ) res[i + 1] = res[i]; res[0] = 0; rep( j, 0, SZ( Md ) ) res[Md[j]] = ( res[Md[j]] - res[k] * _md[Md[j]] ) % MOD; } } rep( i, 0, k ) ans = ( ans + res[i] * b[i] ) % MOD; if ( ans < 0 ) ans += MOD; return ans; } vector< long long > BM( vector< long long > s ) { vector< long long > C( 1, 1 ), B( 1, 1 ); long long L = 0, m = 1, b = 1; rep( n, 0, SZ( s ) ) { long long d = 0; rep( i, 0, L + 1 ) d = ( d + ( long long )C[i] * s[n - i] ) % MOD; if ( d == 0 ) ++m; else if ( 2 * L <= n ) { vector< long long > T = C; long long c = MOD - d * powmod( b, MOD - 2 ) % MOD; while ( SZ( C ) < SZ( B ) + m ) C.push_back( 0 ); rep( i, 0, SZ( B ) ) C[i + m] = ( C[i + m] + c * B[i] ) % MOD; L = n + 1 - L; B = T; b = d; m = 1; } else { long long c = MOD - d * powmod( b, MOD - 2 ) % MOD; while ( SZ( C ) < SZ( B ) + m ) C.push_back( 0 ); rep( i, 0, SZ( B ) ) C[i + m] = ( C[i + m] + c * B[i] ) % MOD; ++m; } } return C; } long long gao( vector< long long > a, long long n ) { vector< long long > c = BM( a ); c.erase( c.begin() ); rep( i, 0, SZ( c ) ) c[i] = ( MOD - c[i] ) % MOD; return solve( n, c, vector< long long >( a.begin(), a.begin() + SZ( c ) ) ); } }; // namespace linear_seq int main() { cin >> n; vector< long long > v; v.push_back( 1 ); v.push_back( 1 ); v.push_back( 2 ); v.push_back( 3 ); v.push_back( 9 ); v.push_back( 16 ); v.push_back( 35 ); v.push_back( 65 ); v.push_back( 143 ); v.push_back( 281 ); v.push_back( 590 ); v.push_back( 1174 ); v.push_back( 2440 ); v.push_back( 4925 ); v.push_back( 10142 ); v.push_back( 20563 ); v.push_back( 42178 ); cout << linear_seq::gao( v, n ) << endl; return 0; } ``` <div class="tip inlineBlock share"> 参考链接：https://blog.csdn.net/qq_41603898/article/details/82722116 </div> ## 魔法 ### 题目描述 #### 原题面 小 Y 正在研究魔法。一个魔法是一个由正整数$[1,d]$组成的序列，长度任意。 一个魔法$A$如果是另一个魔法$B$的子序列，则称这个魔法$A$被魔法$B$包含。 小`Z`给了小`Y`一个长度为$n$的序列。每次给小`Y`两个数$l,r$，表示一个区间$[l,r]$所表示的魔法。小`Z`想知道，最短的不被该区间包含的魔法多长呢？ #### 简明题意 给定一个由正整数$[1,d]$组成的序列，每次询问$[l,r]$所表示的区间，最短的不被该包含的序列的长度。 ### 输入格式 第一行三个正整数数$n,m,d$。表示序列的长度，询问次数，序列的值域。 接下来一行$n$个正整数，表示这个序列。 接下来$m$行一行两个正整数$l,r$。表示询问的区间。 ### 输出格式 输出$m$行。对于每一个询问输出一行一个正整数表示你的答案。 ### 样例 #### 样例输入#1 ```bash 5 4 3 1 2 3 3 1 1 4 1 3 2 5 1 2 ``` #### 样例输出#1 ```bash 2 2 2 1 ``` ### 数据范围 对于$100\%$的数据，$n,m\leq 5\times 10^5,d\leq 100$。 保证除$n,m,d$外，其他数据纯随机。保证存在不依赖数据随机性能通过的算法，时限为标解的两倍以上。 ### 题解 注意到，答案序列（将这个序列记为$B$) 的第一个元素应当出现在$A$的尽星靠后的位置，因为如果出现得过前， 下一个元素会有更多的选择。 那么将$[1, d]$中的每个数字都出现的连续—段分成一组。如$[1, 2, 2, 3, 1, 3, 2, 3](d = 3)$分成$[1, 2, 2, 3], [1, 3, 2]$后的$3$不成—组。 那么为了让出现的元素尽量靠后，选择每一组的最后—个元素即可。那么答案为组数加$1$ 。 考虑分块。预处理块内每个元素跳出块会跳到哪个元素以及会跳几步。就可以用，每—次就能至少跳—个块，优化到$O(m\sqrt{n})$ 。因为每次至少会跳$d$步，可以稍微调大块大小， ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 5; int a[N], fa[20][N], w[20][N], vis[1005]; int main() { int n, m, d; scanf( "%d%d%d", &n, &m, &d ); for ( int i = 1; i <= n; i++ ) scanf( "%d", &a[i] ); int r = 0, cnt = 0; for ( int l = 1; l <= n; l++ ) { while ( r < n && cnt < d ) if ( !vis[a[++r]]++ ) cnt++; fa[0][l] = r + 1; w[0][l] = cnt == d; if ( !--vis[a[l]] ) cnt--; } for ( int i = 0; i <= 19; i++ ) fa[i][n + 1] = n + 1; for ( int i = n; i; i-- ) for ( int j = 1; j <= 19; j++ ) fa[j][i] = fa[j - 1][fa[j - 1][i]], w[j][i] = w[j - 1][i] + w[j - 1][fa[j - 1][i]]; while ( m-- ) { int l, r, ans = 1; scanf( "%d%d", &l, &r ); for ( int i = 19; ~i; i-- ) if ( fa[i][l] - 1 <= r ) ans += w[i][l], l = fa[i][l]; printf( "%d\n", ans ); } return 0; } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/589.html">https://www.starroad.top/archives/589.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：October 23rd, 2020 at 07:18 pm © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
