Black and White
题目链接:
DP
按照常规想法会这样定义状态:dp[当前位数i][当前位是否为黑][连续棋子的个数k]为符合状态的方案数,
但是题目中a,b,n均为1e6,不论空间还是时间都不允许这样做,考虑另外的状态定义:
dp[当前位数i][当前位是否为黑]表示符合状态的合法的方案数;
当前位数大于最大连续棋子数(a,b)时,dp[i][1]=dp[i-1][1]+dp[i-1][0]中包含了连续a个黑棋的非法状态,
而连续a个黑棋的非法状态数与dp[i-a][0]相同(第i-a位到第i位只有均为黑一种情况),将其删去即为合法状态;白棋亦然。
于是状态转移方程为:
- 当i<a&&i<b(从下标1开始)时,
- dp[i][1]=dp[i-1][1]+dp[i-1][0];
- dp[i][0]=dp[i-1][1]+dp[i-1][0];
- 当i>=a||i>=b时,
- dp[i][1]=dp[i-1][1]+dp[i-1][0];
- dp[i][0]=dp[i-1][1]+dp[i-1][0];
- dp[i][1]=dp[i][1]-dp[i-a][0];
- dp[i][0]=dp[i][0]-dp[i-b][1];
代码如下:
1 #include2 #include 3 #include 4 #include 5 #include 6 #define N 1000005 7 using namespace std; 8 typedef long long ll; 9 ll m=1e9+7;10 ll T,a,b,n,dp[N][2];11 int main(void){12 std::ios::sync_with_stdio(false);13 dp[0][1]=dp[0][0]=dp[1][1]=dp[1][0]=1;14 cin>>T;15 while(T--){16 cin>>a>>b>>n;17 for(int i=2;i<=n;++i){18 dp[i][1]=(dp[i-1][1]+dp[i-1][0])%m;19 dp[i][0]=(dp[i-1][1]+dp[i-1][0])%m;20 if(i>=a)dp[i][1]=(dp[i][1]-dp[i-a][0]+m)%m;21 if(i>=b)dp[i][0]=(dp[i][0]-dp[i-b][1]+m)%m;22 }23 cout<<(dp[n][0]+dp[n][1])%m<<"\n";24 }25 }