n个有标号的球围成一个圈。每个球有两种颜色可以选择黑或白染色。问有多少种方案使得没有出现连续白球7个或连续黑球7个。
第一行有多组数据。第一行T表示组数。(T <= 20)
每组包含n，表示球的个数。(1 <= n <= 100000)
每组先输出 "Case #x: " (其中x为当前组数) 该行接下来输出方案数。方案数mod 2015。
解题思路：dp[i][j][k]表示前i个球中，末尾连续j个白球，连续k个黑球的方案数，可以枚举一开始的黑球有几个，然后对后面的进行dp，储存每个答案
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int dp[100015][8][8],ans[100009]; void init() { memset(ans,0,sizeof ans); for(int i=1;i<=6;i++) { memset(dp,0,sizeof dp); dp[i+1][1][0]=1; for(int j=i+1;j<=100010;j++) { for(int k=1;k<=6;k++) dp[j][0][1]=(dp[j][0][1]+dp[j-1][k][0]) 15; for(int k=1;k<=5;k++) dp[j][0][k+1]=(dp[j][0][k+1]+dp[j-1][0][k]) 15; for(int k=1;k<=6;k++) dp[j][1][0]=(dp[j][1][0]+dp[j-1][0][k]) 15; for(int k=1;k<=5;k++) dp[j][k+1][0]=(dp[j][k+1][0]+dp[j-1][k][0]) 15; for(int k=1;k<=6;k++) ans[j]=(ans[j]+dp[j][k][0]) 15; for(int k=1;i+k<7;k++) ans[j]=(ans[j]+dp[j][0][k]) 15; } } } int main() { int n,t,cas=0; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); printf("Case #%d: ",++cas); if(n<=6) printf("%d\n",1<<n); else printf("%d\n",(ans[n]*2) 15); } return 0; }