結果
| 問題 |
No.1035 Color Box
|
| コンテスト | |
| ユーザー |
 simoji
|
| 提出日時 | 2020-04-30 21:39:23 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,371 bytes |
| コンパイル時間 | 2,083 ms |
| コンパイル使用メモリ | 177,136 KB |
| 実行使用メモリ | 13,640 KB |
| 最終ジャッジ日時 | 2024-12-17 18:36:44 |
| 合計ジャッジ時間 | 30,818 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 TLE * 9 |
ソースコード
#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;
}