結果

問題 No.1035 Color Box
ユーザー simojisimoji
提出日時 2020-04-30 21:39:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 9,371 bytes
コンパイル時間 1,957 ms
コンパイル使用メモリ 178,772 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-05-09 23:50:40
合計ジャッジ時間 6,268 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,756 KB
testcase_01 AC 563 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;

long mod = 0;
inline long getDublicatedPatterns(int cubes, int colors){
    long ret = 1;
    for(int i = cubes;i>0;i--){
        ret = ret*colors;
        ret = ret % mod;
        //cout << "i " << i << " colors " <<colors << " ret " << ret << endl;
    }
    //cout << "colors " <<colors << " ret " << ret << endl;
    return ret;
}
void getConbination(int n, int r, vector <int> &v,vector <int> &p,vector <int> &before){
    //cout << "getConbination" << " n " << n << " r " << r << endl; 
    int denomi = 0;
    vector<int>top,bottom;
    for(int i = 0;i<before.size();i++){
        top.push_back(before[i]);
    }
    if(r == 0){
        v.push_back(1);
        return;
    }
    #if 0
    cout << "top :";
    for(int i = 0; i < top.size(); i++){
        cout << top[i] << " ";
    }
    cout << endl;
    #endif
    int tmp = n - r + 1;
    // cout << "hello" << endl;
    // cout << p.size() << endl;
    // cout << before.size() << endl;
    //cout << tmp << endl;
    for(int j=0;j<p.size();j++){
        //cout <<"j:" << j << endl;
        while(tmp%p[j]==0){
            top.push_back(p[j]);
            tmp/=p[j];
            //cout << tmp << " : "<<p[j]<<" : "<<j<< endl;
            if(tmp == 1){
                break;
            }
        }
    }
    #if 0
    cout << "top: ";
    for(int i = 0; i < top.size(); i++){
        cout << top[i] << " ";
    }
    cout << endl;
    #endif
    //cout << "ここまできてる。" << endl;
    //top.push_back(tmp);
    
    tmp = r;
    for(int j=0;j<p.size();j++){
        while(tmp%p[j]==0){
            bottom.push_back(p[j]);
            tmp/=p[j];
        }
        if(j>r){
            break;
        }
    }
    //cout << "aaaa" << endl;
    sort(top.begin(),top.end());
    sort(bottom.begin(),bottom.end());
    //cout << "bbbb" << endl;

    for(int i = 0,j=0; i < bottom.size(); i++){
        // cout << "i:"<<i<<endl;
        // cout << "j:"<<j<<endl;
        // cout << "topSize:"<<top.size()<<endl;
        // cout << "bottomSize:"<<bottom.size()<<endl;
        if(j<top.size()){
            //cout << "ccc" << endl;
            if(top[j]==bottom[i]){
                //cout << "ddd" << endl;
                top[j]=1;
                bottom[i]=1;
                j++;
            }else{
                //cout << "eee" << endl;
                if(top[j]>bottom[i]){
                    //donothing
                    //cout << "fff" << endl;
                }else{
                    while(top[j]!=bottom[i]){
                        //cout << "ggg" << endl;
                        j++;
                        if(j>=top.size()){
                            break;
                        }
                    }
                    //cout << "hhh" << endl;
                    top[j]=1;
                    bottom[i]=1;
                    j++;
                }
            }
        }else{
            break;
        }
    }

    for(int i = 0; i < top.size();i++){
        if(top[i]!=1){
            v.push_back(top[i]);
        }
    }
    #if 0
    for(int i = 0; i < v.size();i++){
        cout << v[i] << " ";
    }
    cout << endl;
    #endif
}

int main(){
    int n,m;
    cin >> n;
    cin >> m;
    //n=3;m=2;
    //cout << 251374071 << endl;
    //cout << "n " << n << " m " << m << endl;
    int numInkBottol = m;
    int numWanabePainted =n;
    long patterns = 1;
    vector <int> primeNumbers;
    mod = (long)pow(10,9)+7;
        //素数をリスト化する。
    //cout << "tst" << endl;
    if (numWanabePainted > numInkBottol) {
        for(long i = 2;i<=n;i++){
            bool isPrime = true;
            for(long j = 2; j < i; j++){
                if(i%j==0){
                    isPrime=false;
                }
            }
            if(isPrime){
                primeNumbers.push_back(i);
                //cout << i << " ";
            }
        }
        vector<int> conbinationFactorize1;
        vector<int> conbinationFactorize2;
        //cout << "path A" << endl;
    
        //patterns = getDublicatedPatterns(numWanabePainted,numInkBottol);
        //cout << patterns << endl;
        int plusMinus = 1;
        conbinationFactorize2 = {1};
        vector<long> nCrRemains;
        vector<long> allPatternsRemains;
        for(int i = 0; i<=numInkBottol;i++){
            long quatient = 0;
            long tmp = 1;
            allPatternsRemains.push_back(getDublicatedPatterns(numWanabePainted,numInkBottol-i)) ;
            if(i%2==0){
                conbinationFactorize1.clear();
                getConbination(numInkBottol,i,conbinationFactorize1,primeNumbers,conbinationFactorize2);
                //cout << i << " : ";
                for(int j = 0; j < conbinationFactorize1.size();j++){
                    //cout << conbinationFactorize1[j] << " ";
                    tmp*=conbinationFactorize1[j];
                    quatient *= conbinationFactorize1[j];
                    quatient += tmp/mod;
                    tmp %= mod;
                }
                nCrRemains.push_back(tmp);
                //cout << " 商 " << quatient << " 余 " << tmp;
                //cout << endl;
            }else{  
                conbinationFactorize2.clear();
                getConbination(numInkBottol,i,conbinationFactorize2,primeNumbers,conbinationFactorize1);
                //cout << i << " : ";
                for(int j = 0; j < conbinationFactorize2.size();j++){
                    //cout << conbinationFactorize2[j] << " ";
                    tmp*=conbinationFactorize2[j];
                    quatient *= conbinationFactorize1[j];
                    quatient += tmp/mod;
                    tmp %= mod;
                }
                nCrRemains.push_back(tmp);
                //cout << " 商 " << quatient << " 余 " << tmp;
                //cout << endl;
            }
        }
        #if 0
        cout << endl;
        for(int i = 0;i <nCrRemains.size();i++){
            cout << nCrRemains[i] << endl;
        }
        cout << endl;
        for(int i = 0;i <allPatternsRemains.size();i++){
            cout << allPatternsRemains[i] << endl;
        }
        #endif

        patterns = 0;
        for(int i = 0; i< allPatternsRemains.size(); i++){
            if(i%2==0){
                patterns+=nCrRemains[i]*allPatternsRemains[i];
                patterns%=mod;
            }else{
                patterns-=nCrRemains[i]*allPatternsRemains[i];
                patterns%=mod;
                if(patterns<0){
                    patterns+=mod;
                }
            }
        }
        //cout << endl;
        cout << patterns << endl;

        #if 0
            conbinationFactorize1.clear();
            getConbination(numInkBottol,0,conbinationFactorize1,primeNumbers,conbinationFactorize2);
            conbinationFactorize2.clear();
            getConbination(numInkBottol,1,conbinationFactorize2,primeNumbers,conbinationFactorize1);
            conbinationFactorize1.clear();
            getConbination(numInkBottol,2,conbinationFactorize1,primeNumbers,conbinationFactorize2);
            conbinationFactorize2.clear();
            getConbination(numInkBottol,3,conbinationFactorize2,primeNumbers,conbinationFactorize1);
        #endif

return 0;
        for(int i = 0; i<= numInkBottol;i++){
            if(i%2==0){
                conbinationFactorize1.clear();
                getConbination(numInkBottol,i,conbinationFactorize1,primeNumbers,conbinationFactorize2);
            }else{
                conbinationFactorize2.clear();
                getConbination(numInkBottol,i,conbinationFactorize2,primeNumbers,conbinationFactorize1);
            }
        }
        return 0;
        for(int i = 1;i < numInkBottol; i++){
            long conbinationModulo = 1;
            if(plusMinus==1){
                conbinationFactorize1.clear();
                getConbination(numInkBottol,i,conbinationFactorize1,primeNumbers,conbinationFactorize2);
                for(int j = 0; j<conbinationFactorize1.size();j++){
                    conbinationModulo*=conbinationFactorize1[j];
                    //conbinationModulo%=mod;
                }
            }else{
                conbinationFactorize2.clear();
                getConbination(numInkBottol,i,conbinationFactorize2,primeNumbers,conbinationFactorize1);
                for(int j = 0; j<conbinationFactorize2.size();j++){
                    conbinationModulo*=conbinationFactorize2[j];
                    //conbinationModulo%=mod;
                }
            }
            patterns = patterns - (plusMinus * conbinationModulo * getDublicatedPatterns(numWanabePainted,numInkBottol-i));
            //patterns = patterns % mod;
            plusMinus *= -1;
            #if 1
                cout <<"i " <<i << " pattern "<<patterns << " conbinationModulo "<<conbinationModulo << endl;
            #endif
        }
        //patterns = patterns % mod;

    }else{
        //cout << "path B" << endl;
        //インクの種類が十分多い
        //順番にインクのバケツにいれる。
        for (int i = numInkBottol; i > 0; i--){
            patterns = patterns * i;
            patterns = patterns % mod;
            #if 0
                cout <<"i " <<i << " pattern "<<patterns << endl;
            #endif
        }
    }
    cout << patterns << endl;
}
0