课后练习题

题目描述

原题

小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

14 1

样例输出#1

3

样例解释#1

解集是$\left\{2,4,14\right\}$。

样例输入#2

1919 810

样例输出#2

7

数据范围

  • 对于$50\%$的数据，$k=1$；
  • 对于$100\%$的数据，$1 \leq k,n \leq 10^{14}$。

代码

#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

4

样例输出#1

9

样例输入#2

1919810

样例输出#2

984599383

数据范围

  • 对于$20\%$的数据，$4 \leq n \leq 10$；
  • 对于$50\%$的数据，$4 \leq n\leq 10^6$；
  • 对于$100\%$的数据，$4 \leq n\leq 10^{18}$。

该题目由于原始代码和题解都没考虑一些情况，下面的错误题这里编辑标签内容解和错误代码仅供娱乐。

错误题解

设$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} $$

代码

#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$）

往后同理。

显然构造矩阵并使用矩阵快速幂。

代码

#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的代码。

#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;
}

魔法

题目描述

原题面

小 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

5 4 3
1 2 3 3 1
1 4
1 3
2 5
1 2

样例输出#1

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$步，可以稍微调大块大小，

代码

#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;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/589.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。

Last modification：October 23, 2020
© Allow specification reprint
如果您觉得我的文章有用，给颗糖糖吧~