题解 | #困难的数学题#
困难的数学题
https://ac.nowcoder.com/acm/contest/16832/C
c题题解
思路
状态表示：f[i] => 组成正整数i的方案数 （组成i：若干个正整数相加得到的和为i） 由题意知：相加序列中的每个数都大于或者等于k 所以可进行集合划分如下： case 1：相加序列中的最后一个数为k.因为减去k之后和为i-k，所以此时的方案数为 f[i-k] case 2：相加序列中的最后一个数大于k，最后一个数减去1之和和为i-1，所以此时的方案数为f[i-1] 综上 Code如下.
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll f[N]; // f[i]：组成正整数i的方案数
int n,k;
int main(){
scanf("%d %d",&n,&k);
f[k]=1; //f[i],i从k开始有效
for(int i=k;i<=n;i++) f[i]=(f[i]+f[i-k]+f[i-1])%mod;
cout<<f[n]<<endl;
return 0;
}
腾讯HR面2290人在聊
投递美团等公司6个岗位