前两题不想写了
数位DP 1003
考虑i的后缀有j个连续，转移状态很简单，滚动数组优化(其实不用)
#includeconst int N = 2e3 + 5;const int MOD = 1000000007;int dp[2][27][4];void add(int &a, int b) { a += b; if (a >= MOD) a -= MOD;}int main() { int T; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); memset (dp, 0, sizeof (dp)); for (int i=1; i<=26; ++i) { dp[1][i][1] = 1; } int now = 1; for (int i=2; i<=n; ++i) { now ^= 1; memset (dp[now], 0, sizeof (dp[now])); for (int j=1; j<=26; ++j) { add (dp[now][j][2], dp[now^1][j][1]); add (dp[now][j][3], dp[now^1][j][2]); for (int k=1; k<=26; ++k) { if (j == k) { continue; } add (dp[now][j][1], dp[now^1][k][1]); add (dp[now][j][1], dp[now^1][k][2]); add (dp[now][j][1], dp[now^1][k][3]); } } } int ans = 0; for (int i=1; i<=26; ++i) { add (ans, dp[now][i][1]); add (ans, dp[now][i][2]); add (ans, dp[now][i][3]); } printf ("%d\n", ans); } return 0;}
约瑟夫环 1004
约瑟夫问题的一个变种，然而题目全部是在唬人，就是一个简单的递推。虽然我知道有人会打表。。。
我们看看裸的约瑟夫是怎么玩的：nn 个人，每隔 kk 个删除。
由于我们只关心最后一个被删除的人，并不关心最后的过程，所以，我们没有必要也不能够模拟整个过程。我们用递推解决。假设有nn个人围成环，标号为[0,n-1][0,n−1]从00开始的好处是取模方便），每数kk个人杀一个的情况下，最后一个存活的人的编号是f[n]f[n]。
我们有f[1]=0f[1]=0,这不需要解释。
接着考虑一般情况f[n]f[n],第一个杀死的人的编号是k-1k−1,杀死后只剩下n-1n−1个人了，那么我们重新编号！
原来编号为k的现在是00号，也就是编号之间相差33我们只要知道现在n-1n−1个人的情况最后是谁幸存也就知道nn个人的情况是谁幸存。幸运的是f[n-1]f[n−1]已经算出来了那f[n]f[n]就是在f[n-1]f[n−1]的基础上加上一个kk即可不要忘记总是要取模。
#includeconst int N = 5e3 + 5;short int dp[N][N];void init() { dp[1][1] = 0; for (int i=2; i<=5000; ++i) { for (int j=1; j<=5000; ++j) { dp[i][j] = (dp[i-1][j+1] + j) % i; } }}int main() { int T; scanf ("%d", &T); init (); while (T--) { int n; scanf ("%d", &n); printf ("%d\n", dp[n][1] + 1); } return 0;}