2015年ブルーブリッジカップ省試合C/C++A組塁サイコロ

11734 ワード

9.サイコロを打つ
賭博聖atmは晩年、サイコロに夢中になった.サイコロをもう一つの上に積み上げ、歪んではいけない.角柱体に積み上げなければならない.長い観察を経て、atmは安定したサイコロの奥義を発見しました:いくつかの数字の面が貼って互いに反発します!まずサイコロを規範化しましょう.1の向こうは4で、2の向こうは5で、3の向こうは6です.m組の反発現象があると仮定すると,各組の2つの数字の面が密着し,サイコロは安定して塁を築くことができない.atmはいくつかの異なる可能性のあるサイコロ方式を計算したいと思っています.2つのバリアサイコロは同じ方式であり、この2つの方式のうち高さに対応するサイコロの対応する数字の向きが同じである場合のみである.シナリオ数が多すぎる場合がありますので、モジュール10^9+7の結果を出力してください.atmのサイコロの数をばかにしないでね～
「入力フォーマット」の1行目の2つの整数n m nはサイコロの数の次のm行を表し、各行の2つの整数a bは、aとbの数字がくっつかないことを示す.
「出力フォーマット」は1行1個の数で、解答モード10^9+7の結果を表します.
「サンプル入力」2 1 1 2
「サンプル出力」544
「データ範囲」30%データ:n<=5 60%データ:n<=100 100%データ:0リソース約定:ピークメモリ消費<256 M CPU消費<2000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.注意:main関数は0を返す必要があります注意:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特殊な関数を呼び出さないでください.注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.コミットするときは、目的のコンパイラタイプを選択することに注意してください.
この問題はまず繰り返すやり方だ.自然に、f[i][j]でi個のサイコロを囲み、一番上のサイコロjを上に向けることができます.では、プッシュは
f[i][j]=∑k=16f[i−1][k]coop[op[j]][k]
内
op[j]表示
jの裏面には、
coop[op[j]][k]は
jの裏は
kは一緒に置いてあります.
このように毎回側面の向きを議論しないので,最後に乗算する.
4n .
うまく実現するには、スクロール配列を使用して配列資料をスクロールします.
検索したコードを入れましょう...

#include 
using namespace std;

// ...    : Compact[i][j]=false     i      j      
bool Compact[7][7];

// ...Parner[i]=j      i          j
const int Parner[7]={ 0,4,5,6,1,2,3 };
const long long MOD = 1000000007;

int main(int argc, char** argv)
{
    long long  N; //     
    int M; //     
    int s1,s2;
    cin >> N >> M;
    for( int i = 0; i < 7; ++i)
        for( int j = 0; j < 7;++j)
            Compact[i][j]=true;

    for( int i = 0; i < M; ++i ) {
        cin >> s1 >> s2;
        // ...   s1      s2      
        Compact[s1][s2] = Compact[s2][s1] = false;
    }
    long long dp[2][7]; //     
    long long C = 4;
    int e = 0;          //     
    for( int i = 1; i < 7; ++i )
        dp[e][i] = 1;

    // dp[i][j]     i ,     j       
    //                   ,                
    int j,k;
    for( long long i = 2; i <= N; ++i ){
        e = 1-e;    // ...    
        C = (C*4)%MOD;
        for( j = 1; j < 7; ++j ){
            dp[e][j] = 0;
            for( k = 1; k < 7; ++k)
                if( Compact[ Parner[j] ][k] )
                    dp[e][j] += dp[1-e][k];
            dp[e][j]%=MOD;
        }

    }
    int sum=0;
    for( int i = 1; i < 7; ++i)
        sum = (sum+dp[e][i])%MOD;
    sum = (sum*C)%MOD;
    cout << sum;
    return 0;
}

コアコードの複雑さT(n)=36 nは,2 sを与えても必ずすべて通過できないので,より速い方法が必要である.分析によると、実際にはステップごとに対応する関係が同じであり、最初に与えられた関係であることが分かった.行列を用いて繰返しを行い,高速べき乗を用いて行列繰返し資料を用いることができる.
コードはテンプレート技術を使っていますが、皆さんは感じてください.の

#include 
using namespace std;

typedef long long ll;
const int MO=1e9+7;
const int opps[]={0,4,5,6,1,2,3};

struct Mat {
    int r,c;
    ll el[10][10];
    Mat() {}
    Mat(ll x) {
        r=c=6;
        memset(el,0,sizeof(el));
        for (int i=1;i<=r;i++) {
            el[i][i]=x;
        }
    }
    Mat(int _r,int _c,ll x) {
        r=_r;c=_c;
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                el[i][j]=x;
            }
        }
    }
    Mat operator *(const Mat &b) {
        Mat res(r,b.c,0);
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=b.c;j++) {
                for (int k=1;k<=c;k++) {
                    res.el[i][j]+=el[i][k]*b.el[k][j];
                }
            }
        }
        return res;
    }
    Mat operator %(const int Mo) {
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                el[i][j]=el[i][j]%Mo;
            }
        }
        return (*this);
    }
    void print() {
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                printf("%I64d ",el[i][j]);
            }
            puts("");
        }
    }
};

template <class DataType>
DataType fpow(DataType x,int n)
{
    DataType res(1);
    while (n) {
        if (n&1) {
            res=x*res%MO;
        }
        x=x*x%MO;
        n>>=1;
    }
    return res;
}

int main()
{
    int n,m;
    Mat coop(6,6,1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        coop.el[x][opps[y]]=0;
        coop.el[y][opps[x]]=0;
    }
    coop=fpow(coop,n-1);
    Mat cnt(6,1,1);
    cnt=coop*cnt%MO;
    ll ans=0,fo=4;
    for (int i=1;i<=6;i++) {
        ans=(ans+cnt.el[i][1])%MO;
    }
    ans=ans*fpow(fo,n)%MO;
    printf("%I64d
",ans);
    return 0;
}

JAvascriptはiphone画面方向に基づいて異なるスタイルシートを呼び出す方法を実現する

css 3フィルタimgアイコンを変色