CCF-CSP-2013-12-4-興味深い数(C++詳細)

2013-12-4-面白い数
問題の説明
私たちは1つの数を面白いと呼んでいます.

その数字は0,1,2,3しか含まれておらず、この4つの数字は少なくとも1回現れたことがある.

すべての0はすべての1の前に現れ、すべての2はすべての3の前に現れた.

の最上位数は0ではありません.したがって、私たちが定義した最小の興味深い数は2013です.それ以外に、4位の面白い数は2つあります:2031と2301.ちょうどnビットの面白い数の個数を計算してください.答えは非常に大きい可能性があるので、100000007の残りを出力するだけです.

入力フォーマット
入力は正の整数n(4≦n≦1000)を含む1行のみである.出力フォーマット出力は1行のみで、ちょうどnビットの整数の面白い数を含む個数を100000007の余数で割った.サンプル入力4サンプル出力3
この問題は、dp(Dynamic Programming)つまりダイナミックプランニングアルゴリズムを使いました.私は、この問題の主な思想は左の数字が右に影響すると思います.そこで、私たちは状況を分けて討論しなければなりません.まず,iが左からi番目,jがj番目の場合を表す2ビット配列sum[i][j]を作成する.それから私たちはテーマを分析して、0は1の前にしなければならなくて、2は3の前にしなければならなくて、その上最初の数字は0ではありませんので、左から最初の数字は必ず2です(これはよく理解するべきです).次に、i番目の数字の前に、左側にはいくつかの数字の構成状況があります.1つ目は2(sum[i][0]で表される)だけです.2つ目は2と0(sum[i][1]で表す)である.3つ目は2と3(sum[i][2]で表す)である.4つ目は2,3,0の3つの数字(sum[i][3]で表される)である.5つ目は2,0,1の3つの数字(sum[i][4]で表される)である.6つ目は2,3,0,1の4つの数字(sum[i][5]で表される).第i位までのすべての状況を分析した後、次に、この6つの状況が第i位に着いたとき、各状況の可能性を分析します.

第1のケース(2):左の数字が2であれば、i位になったときも2であれば、sum[i][0]=1であり、常に1に等しい理由しかない.

第2のケース(2,0):左の数字と第i位の数が2と0で構成されている場合、2と0は制約がないため、第i位に2と0の2つの数字がある場合、すなわちsum[i][1]=(sum[i-1][0]+sum[i-1][1]*2)であり、(j=0)を加えると、左の数字が2の可能性が考えられます.

第3のケース(2,3):左の数字と第i位の数が2と3で構成されている場合、数字2は3より前でなければならないので、条件3を満たす場合はsum[i][2]=(sum[i-1][0]+sum[i-1][2])があり、ここでは1を乗じて省略している.左に2と3がありますが、i位も必ず3を記入しますので、3番目の場合のi位は1番目の場合です×1さらに3つ目のケースを加える×1からなる.第4のケース(2,0,1):左側の数と第i位の数が2,0,1で構成されている場合、0は1より前でなければならないため、第i位より前に2つの状態がある可能性があります.1つは数字2と0で構成されている場合、つまり第2のケースです.二つ目は数字2,0,1からなり,すなわち第4のケースである.この2つの状態のうち、状態1であれば、i位は数字1しか記入できません.状態2であれば、i位は2か1で記入できるので、4番目の場合が必要です×2で,sum[i][3]=(sum[i-1][1]+sum[i-1][3]*2)の4つ目のケースの式を導くことができる.

第5のケース(2,3,0):左側の数と第i位の数が2,3,0から構成されている場合、第i位の前に3つの状態がある可能性があります.1つは数字2と0から構成され、つまり第2のケースです.二つ目は数字2と3からなる、すなわち第3の場合である.三つ目は数字2、3、0からなる、つまり5つ目の場合である.この3つの状態のうち、1と2の状態はいずれも1を乗じたものであり(i番目のビットには1つの数字しか配置できないため)、3番目の状態の場合、i番目の位置には2つの異なる数字(3または0、両者が互いに干渉しないため)、したがって,sum[i][4]=(sum[i−1][1]+sum[i−1][2]+sum[i−1][4]*2)の5つ目のケースの計算式が得られる.

第6のケース(2,0,1,3):第i位の前には(2-3-0)、(2-0-1)、(2-0-1-3)の3つの状態があり、ここで括弧の数字はこれらの数字からなることを表しており、分析により、第i位の前に4つの数字がある場合、第i位は3または1を記入することができ、前の6番目のケースに2を乗じる必要があるので、最終的に得られた6番目のケースの式は以下の通りである:sum[i][5]=(sum[i-1][3]+sum[i-1][4]+sum[i-1][5]*2).

そうそう、毎回数値を求めた後の取り残しを覚えておいてね~

次に私のC++コードを添付します.

#include 
#include 
using namespace std;

int main()
{
     
	int i, n, y = 1000000007;
	long long sum[1001][6];
	cin >> n;
	memset(sum, 0, sizeof(sum));
	for (i = 1; i <= n; i++)
	{
     
		sum[i][0] = 1;
		sum[i][1] = (sum[i - 1][0] + sum[i - 1][1] * 2) % y;
		sum[i][2] = (sum[i - 1][0] + sum[i - 1][2]) % y;
		sum[i][3] = (sum[i - 1][1] + sum[i - 1][3] * 2) % y;
		sum[i][4] = (sum[i - 1][1] + sum[i - 1][2] + sum[i - 1][4] * 2) % y;
		sum[i][5] = (sum[i - 1][3] + sum[i - 1][4] + sum[i - 1][5] * 2) % y;
		/*    （      ）
		printf("sum[%d][0]=1;
",i);
		printf("sum[%d][1]=(sum[%d][0]+sum[%d][1]*2)%%y=%d
",i,i-1,i-1,sum[i][1]=(sum[i-1][0]+sum[i-1][1]*2)%y);
		printf("sum[%d][2]=(sum[%d][0]+sum[%d][2])%%y=%d
",i,i-1,i-1,sum[i][2]=(sum[i-1][0]+sum[i-1][2])%y);
		printf("sum[%d][3]=(sum[%d][1]+sum[%d][3]*2)%%y=%d
",i,i-1,i-1,sum[i][3]=(sum[i-1][1]+sum[i-1][3]*2)%y);
		printf("sum[%d][4]=(sum[%d][1]+sum[%d][2]+sum[%d][4]*2)%%y=%d
",i,i-1,i-1,i-1,sum[i][4]=(sum[i-1][1]+sum[i-1][2]+sum[i-1][4]*2)%y);
		printf("sum[%d][5]=(sum[%d][3]+sum[%d][4]+sum[%d][5]*2)%%y=%d

",i,i-1,i-1,i-1,sum[i][5]=(sum[i-1][3]+sum[i-1][4]+sum[i-1][5]*2)%y);
		*/
	}
	cout << sum[n][5];
	return 0;
}