結果
| 問題 | No.1035 Color Box |
| ユーザー |
 simoji
|
| 提出日時 | 2020-04-30 18:52:38 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,608 bytes |
| コンパイル時間 | 1,794 ms |
| コンパイル使用メモリ | 175,228 KB |
| 実行使用メモリ | 10,752 KB |
| 最終ジャッジ日時 | 2024-05-09 17:58:38 |
| 合計ジャッジ時間 | 6,185 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
10,752 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | AC | 2 ms
5,376 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 | -- | - |
ソースコード
#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 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};
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 0
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;
}