K好数
题目链接
https://www.dotcpp.com/oj/problem2223.html
解题思路
真没想到自己做出来了.
dp[i][j]表示第i位数(从低位到高位),当前位为j的可能.
除了最高位,其他位的每个j都等于前面一位(i-1)与之不相邻数j的和.
最高位的0对应的dp为0,其他的同上.
最后累加求和.
AC代码
#include<bits/stdc++.h> #define ll long long #define sc(x) scanf("%lld",&x) #define pr(x) printf("%lld\n",x) using namespace std; const int mod=1000000007; const int N=105; ll sum,tmp,K,L,dp[N][N],ans; int main(){ sc(K);sc(L); for(ll i=0;i<K;i++) dp[1][i]=1; tmp=K; for(ll i=2;i<=L;i++){ sum=tmp; tmp=0; for(ll j=0;j<K;j++) dp[i][j]=(sum-(j>=1?dp[i-1][j-1]:0)-(j<K-1?dp[i-1][j+1]:0)+mod)%mod,tmp=(tmp+dp[i][j])%mod; } for(ll i=1;i<K;i++) ans=(ans+dp[L][i])%mod; pr(ans); }