結果

問題 No.584 赤、緑、青の色塗り
ユーザー manuginomanugino
提出日時 2017-10-31 21:47:11
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 7,582 bytes
コンパイル時間 719 ms
コンパイル使用メモリ 85,952 KB
実行使用メモリ 49,920 KB
最終ジャッジ日時 2024-11-22 11:13:54
合計ジャッジ時間 2,252 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
49,792 KB
testcase_01 AC 41 ms
49,664 KB
testcase_02 AC 41 ms
49,792 KB
testcase_03 AC 42 ms
49,920 KB
testcase_04 AC 41 ms
49,792 KB
testcase_05 AC 41 ms
49,792 KB
testcase_06 AC 41 ms
49,664 KB
testcase_07 AC 41 ms
49,920 KB
testcase_08 AC 41 ms
49,664 KB
testcase_09 AC 41 ms
49,920 KB
testcase_10 AC 41 ms
49,792 KB
testcase_11 AC 41 ms
49,792 KB
testcase_12 AC 41 ms
49,792 KB
testcase_13 AC 41 ms
49,792 KB
testcase_14 AC 41 ms
49,792 KB
testcase_15 AC 42 ms
49,920 KB
testcase_16 AC 42 ms
49,792 KB
testcase_17 AC 42 ms
49,792 KB
testcase_18 AC 42 ms
49,792 KB
testcase_19 AC 45 ms
49,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



////////////////////////////////////////
//
////////////////////////////////////////

//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) printf("%d\n", (A))
#define prints(A) printf("%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl


#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};

typedef pair<int,int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int INF = (1LL<<31)-1;
const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
const ull INF_ULL = (ull)1e19-1ULL;
const int NONE = -1;
const ll MOD = (ll)1e9+7; //大きい素数の代表といえばこの人、10億7さん

const int N_MAX = 3010; //num of vertex or element
const int M_MAX = 124760; //num of edge
const int DATA_MAX = 1010;



int N;
int R, G, B;

int ans = 0;

ll C[N_MAX][N_MAX]; //combination(n, r)
ll p2[N_MAX]; //pow(2,n)


void init() {
    
    p2[0] = 1;
    rep(i,1,N_MAX) {
        p2[i] = (p2[i-1]*2) % MOD;
    }
    
    rep(i,0,N_MAX) {
        rep(j,0,i+1) {
        
            if(j==0 or j==i) C[i][j] = 1;
            else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    
}


void display() {
#ifdef debug
    dout << "----\n";
    dout << " "; showi(i, 0, N+2);
    show(p2, 0, N+2);
    dout << endl;
    
    dout << "----\n";
    
    dout << "C[][] = \n";
    showi(j, 0, N+2);
    rep(i,0,N+2) {
        dout << "i=" << i << ":";
        rep(j,0,N+2) {
            disP(C[i][j]);
        }
        dout << endl;
    }
    
    
#endif
}





int main() {
    
    //cin, coutの高速化  ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
    cin.tie(0); //cinとcoutの同期を切る
    ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
    
    //read input data
//    scand(N);
    
    din >> N >> R >> G >> B;
    
    
    
    init();
    display();
    

    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
    int s; //sigle colored ■の個数
    int d; //double colored ■■の個数
    int w = N - (R + G + B); //白マスの個数
    int r; //d個の■■のうちRedに塗られるものの個数
    
    for(d=0; d<=(R + G + B)/2; d++) {
        s = (R + G + B) - 2*d;
        
        //敷き詰め切れるか？
        if(d*3+s*2>N+1) continue;
        
        for(r=0; r<=d; r++) {
            if(r<R-s or R<r) continue;
            if(d-r>G or d-r>B) continue;
            
#ifdef debug
            dout << "-----------------------\n";
            disp(d);
            disp(r);
            dout << "---\n";
            disp(s);
            disp(w);
            dout << endl;
            
            dout << "\ndとsを配置する場所の選び方は \n";
            disp(C[w+1][d+s]);
            dout << "\ndとsの並べ方は ";
            disp(C[d+s][d]);
            dout << "\ndのうちr個をRedで塗るが、そのr個の選び方は \n";
            disp(C[d][r]);
            dout << "\ndのうち、Redが塗られなかったd−r個はGreenとBlueで塗ることになる\n";
            dout << "d個について、それぞれの■□と□■の2通りの塗り方があるので、d個全体での塗り方は\n";
            disp(p2[d]);
            dout << "\nsのうちR-r個をRedで塗るが、その選び方は \n";
            disp(C[s][R-r]);
            dout << "\nまだ塗られていないs-R+2r個のうち、Greenに塗るものの選び方は \n";
            disp(C[s-R+2*r][G-d+r]);
            
            dout << "=======\n";
#endif
            ll tmp = C[w+1][d+s];
            (tmp *= C[d+s][d]) %= MOD;
            (tmp *= C[d][r] ) %= MOD;
            (tmp *= p2[d] ) %= MOD;
            (tmp *= C[s][R-r] ) %= MOD;
            (tmp *= C[s-R+2*r][G-d+r] ) %= MOD;
            
            (ans += tmp) %= MOD;
            
#ifdef debug
            dout << "=======\n";
            disp(tmp);
            disp(ans);
#endif
        }
        
    }

    
    
    
#ifdef debug
    dout << "=== OUTPUT ===\n";
#endif
    
    dout << ans << endl;
    
    
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}
0