HDU ACM 2232ロボットの踊り
#include<iostream>
using namespace std;
int base[4][4]={ //
{1,1,0,1},
{1,1,1,0},
{0,1,1,1},
{1,0,1,1}};
int a[2][4][4]; //
void f(int n)
{
int i,j;
if(n==0)
{
for(i=0;i<4;i++)
for(j=0;j<4;j++)
a[1][i][j]=base[i][j];
}
else
{
f(n-1);
for(i=0;i<4;i++)
for(j=0;j<4;j++)
a[0][i][j]=a[1][i][j]%9937;
if(n==1)
return ;
for(i=0;i<4;i++)
{
a[1][i][0]=a[0][i][0]+a[0][i][1]+a[0][i][3];
a[1][i][1]=a[0][i][0]+a[0][i][2]+a[0][i][1];
a[1][i][2]=a[0][i][1]+a[0][i][2]+a[0][i][3];
a[1][i][3]=a[0][i][0]+a[0][i][2]+a[0][i][3];
}
}
}
void solve()
{
int i,j,e,f,sum=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(e=0;e<4;e++)
for(f=0;f<4;f++)
{
if(i==j||i==e||i==f||j==e||j==f||e==f) //
continue;
sum+=(((((a[1][0][i]*a[1][1][j])%9937)*a[1][2][e])%9937)*a[1][3][f])%9937;
sum%=9937;
}
cout<<sum<<endl;
}
int main()
{
int n;
while(cin>>n)
{
f(n);
solve();
}
return 0;
}分析:参照先http://blog.csdn.net/womendeaiwoming/article/details/5806700の詳細な分析を参照してください.
本題:
肝心なところ
格子の位置番号を0 1 3 dp[n][i]としてnステップ後の位置0を表す人が位置iにとどまるシナリオ数dp[n][0]=dp[n-1][0]+dp[n-1][1]+dp[n-1][3]dp[n][1]=dp[n-1][1]+dp[n-1][0]+dp[n-1][2]=dp[n-1][1]+dp[n-1][3]+dp[n-1][2]=dp[n-1][0]+dp[n-1][3]=dp[n-1][0]+dp[n-1][2]+dp[n-1][3]
分かったか?分からなかったら、上の番号を照らし合わせてn歩歩けるとしたら、ロボットがn歩を歩いた後の案は全部でいくらですか.このように考えると、ロボットaのうちの1つが(n−1)ステップに達し、その目標が0番位置であると仮定すると、nステップ目において、0番位置にとどまるスキームの総数は(n−1)ステップによって決定することができる.(n−1)ステップはnステップと1ステップしかないので、歩くことを選択することができ、もちろんその場にとどまることもできる.すなわち、(n-1)では合計3つの位置が1歩通過した後に0番の位置に到達することができ、それぞれ0番、1番と3番で、0番はその場にとどまり、1番は左へ1歩、3番なら上へ1歩進みます.数学で表現すると、つまり上記のように、dp[n][0]=dp[n-1][0]+dp[n-1][1]+dp[n-1][3]、つまり、nステップ後、このロボットが0番位置に到達するシナリオの総数は、(n-1)ステップ時に0番位置にあるシナリオ数+1番位置にあるシナリオ数+3番位置にあるシナリオ数である.1つのロボットが4つの位置に到達できるので、このような式が4つあります.全部で4つのロボットがあります.そうすると、16個あります.
上の式がどうやって来たのか今分かったでしょう.では、もう一度押して、下に押してみましょう.nステップ時のシナリオ総数は(n−1)ステップ時のシナリオ総数で決定されるので,(n−1)時のシナリオ総数は当然(n−2)のシナリオ総数で決定され,(n−2)は(n−3)で決定され,…,(n−(n−2))つまり第2ステップは当然第1ステップ時のシナリオ数で決定される.さあ、第1歩に着きました.これは指で計算できるでしょう.直接書いてください.これですべての案数が確定した(また押し返せば解ける).
各号の位置にいるロボットがnステップを経て各号の位置に到達するシナリオの総数を知った後、実行可能なシナリオの数を合計すればよい.ロボットの位置が合法的なのは全部で4!=24種類です.一つの位置にロボットが必要だから!例えば、0番ロボットは1番位置、1番ロボットは0番位置、2番、3番ロボットは位置が変わらないことも可能です.このような合法的な案をすべて列挙すると24種類(0番位置4個(4個のロボットはどちらから0番位置までも可能)*1番位置3個(0番位置が確定している機械があるため、もう1番位置まで上がることは不可能)*2番位置2個*3番位置1個)、つまり4*3*2*1=24
それぞれの合法的な状況の方案の総数はすべての機械が到着した位置の方案の数を乗じて得られます!最后に24の情况をすべて合わせて、解を得ます!もちろん、nは少し大きくて、案はとても大きくて、すべてのテーマも9937に型を取ると言っています.
総じて言えば、思想は複雑ではなく、難しくもない.しかし、その中のおまかせの関係が見つからないといえば、本当に手がつけられない.指で計算しても、0歩で1種類、1歩で9種類、2歩で633種類になりますが、指を何枚に分けなければなりませんか?ほほほ、2歩しか歩かないのにこんなに多い案は想像しにくいでしょう.少なくとも私は考えられない!
次のコードを説明します.
int B[4][4]={
i/j 0 1 2 3 0 {1,1,0,1}, 1 {1,1,1,0}, 2 {0,1,1,1}, 3 {1,0,1,1} };ここではi行,j列を表す.n=1でi番位置にロボットがj番位置に留まるシナリオ数.i=0というのは、0番の位置にあるロボットが1歩進んだ後にjに到達するシナリオ数を表し、j=0となり、その場に留まる、という1つのシナリオです.j=1を右に移動する1つのシナリオ.j=2,1歩も届かない、0案.j=3,上向き移動,1つのスキーム,すなわち,1,1,0,1上の2次元行列をこれにより推定した.n=1が決定され,上記の推論により,後のn>1のステップ数はいずれもn=1によって押し出される.n=1の場合を既知の条件とする必要があります
中には型取りに関する質問もあります:a*b%c=a%c*b%c、なぜこのようにすることができるのか、私はここで疲れていません.
レベルが高くなく、よくわからないことや間違ったことを言っているところもありますので、ご指摘ください.
次のコードはめちゃくちゃです
[cpp] view plain copy
#include
using namespace std;
int B[4][4]={//n=1で各位置のロボットが各位置に到達するシナリオ数 {1,1,0,1},
{1,1,1,0},
{0,1,1,1},
{1,0,1,1}
};
struct In{
int A[4][4];
};
In a,b;//a,bそれぞれ1ステップ、2ステップ……nステップを記録するためのシナリオ数void f(int n)/まず最初のステップをaに求め,次にaから後のステップを求めるときのシナリオ数をbで記し,nステップを再帰的に求める.
{
int i,j;
if(n==0)
{
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
b.A[i][j]=B[i][j];
}
}
}
else
{
f(n-1);
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
a.A[i][j]=b.A[i][j];
a.A[i][j]%=9937;//データが大きすぎる場合、型取り }
}
if(n==1)
return ;
for(i=0; i<4; i++)
{
b.A[i][0]=a.A[i][0]+a.A[i][1]+a.A[i][3];
b.A[i][1]=a.A[i][0]+a.A[i][2]+a.A[i][1];
b.A[i][2]=a.A[i][1]+a.A[i][2]+a.A[i][3];
b.A[i][3]=a.A[i][0]+a.A[i][2]+a.A[i][3];
}
}
}
void Solve()
{
int i,j,e,f,sum=0;
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
for(e=0; e<4; e++)
{
for(f=0; f<4; f++)
{
if(i==j|=i==e|i==f||j==e|j==f|=e==f)/各位置にロボットが1つ必要です
continue;
sum+=((((((b.A[0][i]*b.A[1][j])%9937)*b.A[2][e])%9937)*b.A[3][f])%9937)%9937;//境界を越えるのを防止するには、2つのスキームごとに乗算しなければならない sum%=9937;
}
}
}
}
cout<
}
int main()
{
int n;
while(cin>>n)
{
f(n);
Solve();
}
return 0;
}