首页 > 试题广场 >

填数游戏

[编程题]填数游戏

热度指数：1509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团和小美正在玩一个填数游戏，这个游戏是给一个等式，其中有一些数被挖掉了，你需要向其中填数字，使得等式成立。

比如 ___+12=34，那么横线填的一定是22

现在，这个游戏到了最后一关，这一关的等式很奇特：_+_+_+...+_=n

这里可以填任意多个正整数（甚至可能是1个），只要这些数的和等于n即可。

但是，有一个额外的限制，填入的所有数必须小于等于k，大于等于1，填入的数的最大值必须大于等于d。

请你计算，有多少个不同的等式满足这些限制。由于答案可能很大，请将答案mod(998244353)后输出。

输入描述:

输入包含三个数n, k, d

输出描述:

输出包含一行，即方案数。

示例1

输入

5 3 2

输出

说明

2+3=5
3+2=5
1+1+3=5
1+3+1=5
3+1+1=5
1+2+2=5
2+1+2=5
2+2+1=5
1+1+1+2=5
1+1+2+1=5
1+2+1+1=5
2+1+1+1=5
共12种填法

备注:

对于40%的数据，
对于100%的数据，

算法知识视频讲解

4fbd81e

给你 $n,k,d$
让你求带限制的 $n$ 的Composition个数，限制是 $1\leq sum.\leq k$ && $\text{max}\ sum.\geq d$
由于答案可能很大，请将答案mod(998244353)后输出。

思路：

n做Compostion且和数在[1,r]范围内的方案数目是 $C_{n}^{\{1, \ldots, r\}}= \sum_{j, k}(-1)^{k}\left(\begin{array}{l} j \\ k \end{array}\right)\left(\begin{array}{c} n-r k-1 \\ j-1 \end{array}\right)$

n做Compostion且最大的和数是 $r(r\geq 1)$ 的方案数目是 $C_{n}^{\{\text{max}\ sum.=r\}}=C_{n}^{\{1, \ldots, r\}}-C_{n}^{\{1, \ldots, r-1\}}$
n做Compostion且最大的和数在 $[Left,Right]$ 的方案数目是 $C_{n}^{\{\text{max}\ sum.\in[Left,Right]\}}=C_{n}^{\{1, \ldots, Right\}}-C_{n}^{\{1, \ldots, Left-1\}}$

//直接出击，算那个doubel combinomial sum
//这题数据放水所以这份代码AC了囧，别骂了别骂了
//感觉最有效的做法是dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 998244353
ll n,k,d;
ll b[10005][10005];
ll ans=0;
void GetBinomial(){
    for(int i=0;i<=1005;i++) b[i][0]=1;
    for(int  i=1;i<=1005;i++){
        for(int  j=1;j<=i;j++){
            b[i][j]=(b[i-1][j]+b[i-1][j-1])%mod;
        }
    }
} 

ll Comp_n_of_Range1R(ll n,ll r){//n做Compostion且和数在[1,r]范围内的方案数目 
    if(r==0) return 0;
    ll sum=0;
    for(ll k=0;k<=(n-1)/r;k++){
        for(ll j=k>1?(k):1 ;j<=n-r*k;j++){
            if(k&1){
                sum=(sum+mod-b[j][k]*b[n-r*k-1][j-1]%mod)%mod;     
            }
            else {
                sum=(sum+b[j][k]*b[n-r*k-1][j-1]%mod)%mod;
            }
            //cout<<"sum"<<sum<<endl;
        }
    }
    return sum;
}





int main(){
    GetBinomial();
//    for(ll i=1;i<=10;i++){
//        for(ll j=0;j<=i;j++){
//            cout<<b[i][j]<<" ";
//        }
//        puts("");
//    }

    cin>>n>>k>>d;
    if(d<1||k<0||d>k) {
        ans=0;
        cout<<ans<<endl;
    }
    else{
        ll l=d;
        ll r=k;
            ans=(ans+Comp_n_of_Range1R(n,r)-Comp_n_of_Range1R(n,l-1)+mod)%mod; 
        cout<<(ans+mod)%mod<<endl;
    } 

    return 0;
}

编辑于 2021-03-08 16:15:15 回复(0)

pein531

动态规划求解，构建一个(n+1)*2的dp数组，dp[i][0]表示凑出i时没有使用大于等于d的数的方案数，dp[i][1]表示凑出 i 时用了大于等于d的数的方案数。在凑某个数i时，状态转移有如下情况：

(1) 如果此时要填的数 j<d：

因为凑成 i 没有使用大于等于 d 的数，那凑成 i-j 也没有使用大于等于 d 的数，dp[i][0]只会从dp[i-j][0]转移过来，dp[i][1]也只会从dp[i-j][1]转移过来。而这种填数游戏在 i-j 的填数方案已经确定的情况下，现在要填数 j 应该满足累加的原则，所以在遍历 j 时，j 每取一个值就把前面的方案数加一次，状态转移方程为：

dp[i][0] = dp[i][0] + ∑dp[i-j][0]

dp[i][1] = dp[i][1] + ∑dp[i-j][1]

(2) 如果此时要填的数 j>=d：因为现在要填的 j 已经满足大于等于 d 了，所以填数方案中至少得有一个数大于等于d的成就已经达成，凑成 i-j 有没有使用大于等于 d 的数已经不重要。此时只更新dp[i][1]，dp[i][1]可以从dp[i-j][0]和dp[i-j][1]两个状态转移过来，状态转移方程为：

dp[i][1] = dp[i][1] + ∑(dp[i-j][0]+dp[i-j][1])。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int k = Integer.parseInt(params[1]);
        int d = Integer.parseInt(params[2]);
        // dp[i][0]表示凑成i时没有用大于等于d的方案数，dp[i][1]表示凑成i时用了大于等于d的方案数
        long[][] dp = new long[n + 1][2];
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            // 题目要求填的正整数范围是从1~k，但是也不能超过目标值i
            for(int j = 1; j <= Math.min(k, i); j++){
                if(j < d){
                    dp[i][0] = (dp[i][0] + dp[i - j][0]) % 998244353;
                    dp[i][1] = (dp[i][1] + dp[i - j][1]) % 998244353;
                }else
                    dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % 998244353;
            }
        }
        // 输出凑出了n并且使用了大于等于d的数的方案数
        System.out.println(dp[n][1]);
    }
}

编辑于 2021-03-13 10:56:26 回复(6)

只想拿个offer啊

经典动态规划

只需计算出使用1到k构成和为n的方案, 然后减去其中的非法方案

不合法方案为使用1到d-1构成和为n的方案

两次动态规划即可求解

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
const int MOD = 998244353;

void solve(){
    int n, k, d;
    cin >> n >> k >> d;
    vector<int> all(n + 1), low(n + 1);
    all[0] = low[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= min(k, i); j ++ )
            all[i] = (all[i] + all[i - j]) % MOD;
        for (int j = 1; j <= min(d - 1, i); j ++ )
            low[i] = (low[i] + low[i - j]) % MOD;        
    }
    int ans = (all[n] - low[n]) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

发表于 2021-10-18 11:24:35 回复(2)

努力进大厂的萌新

//题意：num ,[1,k],最填入数的最大值大于等于d;
/*
完全背包，重量为n,物品为【1，k】 && max(num) >= d;求排列数，即一个数必定为【d,k】,其他的数【1，k】

等价为【1，k】，和为n的总和 - 【1，d-1】和为n的总和
*/

#include<bits/stdc++.h>

using namespace std;

const int MOD  = 998244353;

//总和为n,物品为【1，y】的完全背包总数
long long  getnums(int n,int y){
    vector<long long >dp(n + 1,0);
    dp[0] = 1;
    //求排列数，先遍历背包，再遍历物品
    for(int i = 1;i <= n;i++){
        //遍历物品
        for(int j = 1 ;j <= y;j++){
            if(i >= j) dp[i] = (dp[i] + dp[i - j])%MOD;
        
        }
    }
    /*for(int i = 0 ;i < n;i++){
        cout << dp[i] << ",";
    }*/
    return dp[n];
}

int main(){
    long long  n ,k ,d;
    cin >> n >> k >> d;
    long long  ans = getnums(n,k)- getnums(n,d - 1);
    ans = (ans + MOD) % MOD;
    cout << ans <<endl;
    return 0;
}

发表于 2022-04-01 21:44:19 回复(1)

Lysen-Goto

动态规范（Java 版）

import java.util.Scanner;
 
public class Main {
    private static int result = 0;

    // 动态规划
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt(), d = scanner.nextInt();
        // dp[i][0] 表示和为 i 且最大值小于 d 的总数目
        // dp[i][1] 表示和为 i 且最大值大于等于 d 的总数目
        long[][] dp = new long[n+1][2];
        // 初始化
        dp[0][0] = 1; dp[0][1] = 0;
        // 遍历
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k && j <= i && j < d; ++j) {
                dp[i][0] += dp[i-j][0];
            }
            dp[i][0] %= 998244353;
            for (int j = 1; j <= k && j <= i; ++j) {
                dp[i][1] += j < d ? dp[i-j][1] : (dp[i-j][0] + dp[i-j][1]);
            }
            dp[i][1] %= 998244353;
        }
        // 结果
        System.out.println(dp[n][1]);
    }
}

发表于 2023-07-27 11:13:10 回复(0)

wonderson

贡献个简单的思路：记忆化搜索。

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(), k = sc.nextInt(), d = sc.nextInt();
            sc.close();
            f = new int[n + 1][2];
            for (int i = 0; i < n + 1; i++) {
                Arrays.fill(f[i], -1);
            }
            int res = dfs(n, 0, 1, k, d);
            System.out.println(res);
        }

        private static int MOD = 998244353;
        private static int[][] f;
        private static int dfs(int cur, int has, int lo, int hi, int d) {
            if (f[cur][has] >= 0) {
                return f[cur][has];
            }

            if (cur == 0) {
                int t = has == 1 ? 1 : 0;
                f[cur][has] = t;
                return t;
            }

            int res = 0;
            for (int i = lo; i <= hi; i++) {
                if (cur >= i) {
                    if (i >= d) {
                        res = (res + dfs(cur - i, 1, lo, hi, d)) % MOD;
                    } else {
                        res = (res + dfs(cur - i, has, lo, hi, d)) % MOD;
                    }
                } else {
                    break;
                }
            }
            
            f[cur][has] = res;
            return res;
        }
    }

发表于 2022-04-12 18:31:23 回复(0)

牛客514597917号

#include<bits/stdc++.h>;
using namespace std;
int main(){
int n,k,d;
cin >>n>>k>>d;
long long* dfs_all = new long long[n+1];
long long* dfs = new long long[n+1];
dfs_all[0]=1;
for(int i =1;i<=n;i++){
for(int j =1;j<=min(k,i);j++){
if(j<d){
dfs[i] = (dfs[i-j]+dfs[i])%998244353;
dfs_all[i] = (dfs_all[i-j]+dfs_all[i])%998244353;
}else{
dfs[i] = (dfs_all[i-j]+ dfs[i-j]+dfs[i])%998244353;
}
}
}
cout <<dfs[n]%998244353<<endl;
}

发表于 2022-05-31 20:21:38 回复(0)

SparkElf

还算漂亮

#include<bits/stdc++.h>
using namespace std;
const unsigned N = 1e3 + 1;
const unsigned Mod = 998244353;
int memo[N][2];//第二个维度是前面的maxV>=d与否
int main() {
    int n, k, d;
    cin >> n >> k >> d;
    memset(memo, -1, sizeof(memo));
    function<int(int, bool)> dfs = [&](int target, bool flag)->int {//是排列不是组合 998244353*2<2 147 483 648
        int count = 0;
        int newT, newFlag;
        for (int i = 1; i <= k; i++)
        {
            newT = target - i;
            newFlag = (flag || i >= d);
            if (newT < 0)break;
            else if (newT == 0) {
                count += newFlag;
                count %= Mod;
                break;
            }
            else if (memo[newT][newFlag] != -1) {
                count += memo[newT][newFlag];//完全背包的记忆化只有一个维度
            }
            else {
                count += dfs(newT, newFlag);//newT为0不能被记忆
            }
            count %= Mod;
        }
        memo[target][flag] = count;
        return count;
    };
    cout << dfs(n, 0) << endl;
    return 0;
}

发表于 2022-04-05 00:17:12 回复(0)

看星星呐

感谢楼上大佬思路

n,k,d = map(int, input().split())
a1 = [1]+[0]*(n)  #没有使用大于等于d的数去凑
a2 = [0]*(n+1)  #使用了大于等于d的数去凑
for i in range(1,n+1):
    for j in range(1,min(k,i)+1):
        if j<d:
            a1[i] = (a1[i] + a1[i-j]) % 998244353
            a2[i] = (a2[i] + a2[i-j]) % 998244353
        else:
            a2[i] = (a2[i] + a1[i-j] + a2[i-j]) % 998244353
print(a2[n])

发表于 2021-09-01 09:44:41 回复(0)

Python

maoxiaomao

python 递归解法...

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
@lru_cache(None)  
def dfs(v,flag):
    if v>n:return 0
    if v==n and flag:return 1
    if v==n and not flag:return 0
    ans=0
    for i in range(1,k+1):
        if i>=d:
            ans+=dfs(v+i,True or flag)
        else:
            ans+=dfs(v+i,False or flag)
    return ans % 998244353
n,k,d=map(int, input().strip().split())
ans=dfs(0,False)
print(ans)

编辑于 2021-08-06 14:14:36 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师美团前端工程师算法工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

10条回答 45收藏 4338浏览

通过挑战的用户

牛客85284...

2023-03-11 10:02:57
孟德尔小豌豆

2023-03-09 19:56:28
江湖之水

2023-03-07 20:20:25
巴布鲁斯

2023-03-04 12:12:53
奋斗的龙猫

2023-02-13 14:23:05