結果

問題 No.1035 Color Box
コンテスト
ユーザー simoji
提出日時 2020-04-30 18:37:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,304 bytes
コンパイル時間 2,308 ms
コンパイル使用メモリ 175,636 KB
実行使用メモリ 16,960 KB
最終ジャッジ日時 2024-12-16 07:58:51
合計ジャッジ時間 37,571 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 4 WA * 23 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

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]);
    }
    int tmp = n - (r-1);
    // cout << "hello" << endl;
    // cout << p.size() << endl;
    // cout << before.size() << endl;
    // cout << tmp << endl;
    for(int i = 0; i< p.size();i++){
        //cout << p[i] << " ";
    }
    //cout << 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(j>r){
            break;
        }
    }
    //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 1
    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;
        //素数をリスト化する。
    for(int i = 2;i<=n;i++){
        bool isPrime = true;
        for(int 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;
    if (numWanabePainted > numInkBottol) {
    
        patterns = getDublicatedPatterns(numWanabePainted,numInkBottol);
        cout << patterns << endl;
        int plusMinus = 1;
        conbinationFactorize2 = {1};
        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
        }

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