题意：
现在要挑选n个士兵成为一个排列，从三个不同的军团之中，第一个军团最少u个人连续站在一起，第二个军团最多有v个士兵站在一起，问有多少种不同的挑选方式。
思路：
对于最多和最少问问题尽量转化为最多的问题，比如第一个军团的限制条件，那么在求的时候转化为最多有i个人。
排列组合计数问题很容易从前一个状态推到当前的状态，定义: dp[i][0] 表示第i个人是第一军团的组合数， dp[i][1] 表示第i个人是第二军团的组合数， dp[i][2] 表示第i个人是第三军团的组合数。那么就可以通过前一个人是谁推导当前的可能数。
解决的办法是判断当前有多少人，减去不满足条件的即可。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1000000+10; const int mod = 1000000007; long long dp[maxn][3]; int n; long long solve(int u,int v) { dp[0][0] = 1; dp[0][1] = 0; dp[0][2] = 0; for(int i = 1;i <= n; i++) { long long sum = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%mod; dp[i][2] = sum; if(i <= u) dp[i][0] = sum; else if(i == u+1) dp[i][0] = (sum-1)%mod; else dp[i][0] = (sum - dp[i-u-1][1] - dp[i-u-1][2])%mod; if(i <= v) dp[i][1] = sum; else if(i == v + 1) dp[i][1] = (sum - 1)%mod; else dp[i][1] = (sum - dp[i-v-1][0] - dp[i-v-1][2])%mod; } return (dp[n][0]+dp[n][1]+dp[n][2])%mod; } int main() { // freopen("in.txt","r",stdin); int u,v; while(scanf("%d%d%d",&n,&u,&v) != EOF) { long long ans = solve(n,v); ans = ((ans-solve(u-1,v))%mod+mod)%mod; printf("%I64d\n",ans); } return 0; }