結果
| 問題 | No.1035 Color Box |
| ユーザー |
 simoji
|
| 提出日時 | 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 | -- | - |
ソースコード
#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;
}