提高组2020-01-20NOIP测试

Author：薇薇安
发布时间：January 22, 2020
284views
No comments
3295 words
Categories：题解

毒瘤测试又一场。

## 课后练习题

### 题目描述

#### 原题

小`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}$。

!> 该题目由于原始代码和题解都没考虑一些情况，下面的错误题解和错误代码仅供娱乐。

### 错误题解

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

[album]

![1-1][13]
[/album] </div>
</div><div role="tabpanel" id='tabs-faaa6bccb2c2a2f5cc2365c7205e90aa191' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![2-1][14]
[/album] </div>
</div><div role="tabpanel" id='tabs-ab49b8b48f0c785494a41e4392b0166142' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![3-1][15]
![3-2][16]
![3-3][17]
![3-4][18]
[/album] </div>
</div><div role="tabpanel" id='tabs-6781fd2bfc553db70328723bc6dc242a113' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![4-1][19]
![4-2][20]
[/album] </div>
</div><div role="tabpanel" id='tabs-edffdb5dac51bc42f09a4ba46f7e9abc804' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![5-1][21]
![5-2][22]
![5-3][23]
[/album] </div>
</div>
</div>
</div>

往后同理。

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

#### 代码

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

@> 参考链接：https://blog.csdn.net/qq_41603898/article/details/82722116

## 魔法

### 题目描述

#### 原题面

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

[1]: https://www.oss.starroad.top/usr/uploads/2020/01/205434492.png
[2]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[3]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[4]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[5]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[6]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[7]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[8]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[9]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[10]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[11]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[12]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[13]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[14]: https://www.oss.starroad.top/usr/uploads/2020/01/2928758477.png
[15]: https://www.oss.starroad.top/usr/uploads/2020/01/205468517.png
[16]: https://www.oss.starroad.top/usr/uploads/2020/01/1094960209.png
[17]: https://www.oss.starroad.top/usr/uploads/2020/01/4128052238.png
[18]: https://www.oss.starroad.top/usr/uploads/2020/01/1480838697.png
[19]: https://www.oss.starroad.top/usr/uploads/2020/01/3475515577.png
[20]: https://www.oss.starroad.top/usr/uploads/2020/01/2149808833.png
[21]: https://www.oss.starroad.top/usr/uploads/2020/01/2075953566.png
[22]: https://www.oss.starroad.top/usr/uploads/2020/01/3170184189.png
[23]: https://www.oss.starroad.top/usr/uploads/2020/01/987037816.png
[24]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[25]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[26]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[27]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[28]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[29]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[30]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[31]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[32]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[33]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[34]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[35]: https://www.oss.starroad.top/usr/uploads/2020/01/2928758477.png
[36]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[37]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[38]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[39]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[40]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png
[41]: https://www.oss.starroad.top/usr/uploads/2020/01/4198365561.png

<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：February 1st, 2020 at 10:30 am

如果您觉得我的文章有用，给颗糖糖吧~

提高组2020-01-20NOIP测试

薇薇安 • 2020 年 01 月 22 日

毒瘤测试又一场。

## 课后练习题

### 题目描述

#### 原题

#### 简明题意

求如下方程**正整数**解的个数。
$$
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}$。

### 代码

分情况考虑统计因数个数即可。

## 拼图

### 题目描述

#### 原题面

小`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}$。

!> 该题目由于原始代码和题解都没考虑一些情况，下面的错误题解和错误代码仅供娱乐。

### 错误题解

设$f_x$为拼$4\times x$的模板的方案数。

根据画画可知递推式$f_x=f_{x-1}+f_{x-2}+f_{x-4}\times 4$。

#### 代码

### 正确题解（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$）

[album]

![1-1][13]
[/album] </div>
</div><div role="tabpanel" id='tabs-f79ed927f15a80256a10d25d34308f9e331' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![2-1][14]
[/album] </div>
</div><div role="tabpanel" id='tabs-b124311a0eccc5664cee90c00ee1a961432' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![3-1][15]
![3-2][16]
![3-3][17]
![3-4][18]
[/album] </div>
</div><div role="tabpanel" id='tabs-826107d06d65b6d6c2a7a545a49c3436773' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![4-1][19]
![4-2][20]
[/album] </div>
</div><div role="tabpanel" id='tabs-80dc1a20d543925609a67443693e3e93974' class="tab-pane fade  ">
            
<div class='album_block'>

[album]

![5-1][21]
![5-2][22]
![5-3][23]
[/album] </div>
</div>
</div>
</div>

往后同理。

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

#### 代码

### 正确题解（By钟神）

既然肉眼无法看出递推式。那么暴力搜索前面的结果。然后用`杜教BM`暴力推出递推式。

`BM`推线性递推式，最低阶的复杂度好像是$n^2log_2n$。$n$是输入项数，比高斯消元算快很多。

下面附上`杜教BM`的代码。

@> 参考链接：https://blog.csdn.net/qq_41603898/article/details/82722116

## 魔法

### 题目描述

#### 原题面

小 Y 正在研究魔法。一个魔法是一个由正整数$[1,d]$组成的序列，长度任意。

一个魔法$A$如果是另一个魔法$B$的子序列，则称这个魔法$A$被魔法$B$包含。

小`Z`给了小`Y`一个长度为$n$的序列。每次给小`Y`两个数$l,r$，表示一个区间$[l,r]$所表示的魔法。小`Z`想知道，最短的不被该区间包含的魔法多长呢？

#### 简明题意

给定一个由正整数$[1,d]$组成的序列，每次询问$[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$ 。

### 代码

提高组2020-01-20NOIP测试

Leave a Comment Cancel reply

Handsome静态资源加速

Handsome 主题使用阿里云镜像加速

成都外国语学校信息学集训课 Day13

洛谷自动打卡机

化学预习（初中第十单元【酸和碱】）

刷题清单

成都外国语学校信息学夏令营 Day4

成都外国语学校信息学夏令营 Day3

最后一次讲演（泡面版）

zzy大佬的语录

提高组2020-01-20NOIP测试