课后练习题

题目描述

原题

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

Last modification:October 23rd, 2020 at 07:18 pm
如果您觉得我的文章有用,给颗糖糖吧~