本来以为是组合数学的题，结果被一个至多一个至少搞得无从下手，后来学习到可以将至少转化为至多：在n个元素里面至少有m个a等价于在n个元素里面至多有n个a-在n个元素里至多有n-m个a。另外就是比较常见的取模问题：可简单的认为做一次运算就取一次模。减法运算为了防止出现负数，在模完后还要再加上模数再取一次模。#include using namespace std; const long long M = 1000000007; const long long N = 1000000; long long s[N][3]; long long solve(long long n, long long m, long long k){ long long sum; s[0][0] = 1, s[0][1] = 0, s[0][2] = 0; for(int i = 1; i <= n; i ++){ sum = (s[i - 1][0] + s[i - 1][1] + s[i - 1][2]) % M; s[i][2] = sum; if(i <= m) s[i][0] = sum; else if(i == m + 1) s[i][0] = (sum - 1) % M; else s[i][0] = (sum - s[i - m - 1][1] - s[i - m - 1][2]) % M; if(i <= k) s[i][1] = sum; else if(i == k + 1) s[i][1] = (sum - 1) % M; else s[i][1] = (sum - s[i - k - 1][0] - s[i - k - 1][2]) % M; } return (s[n][0] + s[n][1] + s[n][2]) % M; } int main(){ long long n, m, k; long long ans1, ans2; while(cin >> n >> m >> k){ ans1 = solve(n, n, k); ans2 = solve(n, m - 1, k); cout << ((ans1 - ans2) % M + M) % M << endl; } return 0; }

二周目，这次对一些事情进行更详细地说明，首先就是最多最少的转换上，题目虽然说最少m个，但其实这是两个条件——大于等于m且小于等于n，借助这个才可以推出最少m个时的组合数 = 最多n个的组合数 - 最多m - 1个的组合数。第二点，对于dp数组的初始化，显然对于第一个位置，各个兵团都只有一种排列方法。第三点，取模，ans1 可能小于ans2，所以要加上M再取模，ans1 - ans2 的绝对值可能大于M，所以要先对他们的差取模然后加上M再一同取模