题解：CF1997F Chips on a Line

· · 题解

观察发现如下事实：

因此，所有棋子的花费与提供都是若干个 1 号棋子。由操作性质和积累可知，棋子 i 花费为斐波那契数 f_i。

由于 f_{10}=55，至多 55000 个 1 号棋子，查表或打表可知用到的位置不会超过 24。

预处理出用 0\sim 55000 个 1 号棋子可以得到的最少棋子个数。

之后统计出恰好 i 个棋子的方案数目，具体的，定义 dp_{i,j,k} 表示到第 i 个位置为止，用了 j 个棋子，产生 k 个 1 号棋子的方案数。可以优化掉 i 这一维度，之后直接转移得到结果。

最后根据 1 号棋子个数是否满足条件直接累加即可。

预处理运算量为 24 \times 55000，剩下的复杂度为 \Theta(xn^2)

为了节省篇幅，代码中 mint 表示取模整数。完整代码在这里。

#include<bits/stdc++.h>
using namespace std;
namespace _wrk{;
#define int long long
#define mod 998244353
#define mint modint<mod>
Math<mint,1000006>math;
int a[2323];
int n,m,x;
int c[60000];
mint p[1003][60003];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    a[1]=a[2]=1;
    for(int i=3;i<=24;i++){
        a[i]=a[i-1]+a[i-2];
    }
    memset(c,0x3f,sizeof(c));
    c[0]=0;
    for(int k=1;k<=24;k++){
        for(int i=a[k];i<=a[10]*1000;i++){
            c[i]=min(c[i],c[i-a[k]]+1);
        }
    }
    int n,m,x;
    cin>>n>>x>>m;
    p[0][0]=1;
    for(int i=1;i<=x;i++){
        for(int f=1;f<=n;f++){
            for(int j=a[i];j<=55*n;j++){
                p[f][j]+=p[f-1][j-a[i]];
            }
        }
    }
    mint ans=0;
    for(int i=1;i<=a[10]*1000;i++){
        if(c[i]==m)ans+=p[n][i];
    }
    cout<<ans;

    return 0;
}
}
signed main(){
       return _wrk::main();
}