結果
| 問題 | No.303 割れません |
| ユーザー |
 mamekin
|
| 提出日時 | 2016-02-11 01:09:52 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,008 bytes |
| コンパイル時間 | 2,390 ms |
| コンパイル使用メモリ | 113,432 KB |
| 実行使用メモリ | 817,280 KB |
| 最終ジャッジ日時 | 2024-09-22 00:13:16 |
| 合計ジャッジ時間 | 5,021 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | MLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
ソースコード
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;
static const double PI = acos(-1.0);
class Bigint
{
private:
static const int LEN = 7;
static const int MAX = 10000000;
vector<long long> a;
bool sign;
void normalize(){
while(!a.empty() && a.back() == 0)
a.pop_back();
if(a.empty())
sign = true;
}
Bigint(const vector<long long>& x){
a = x;
sign = true;
normalize();
}
void dft(const vector<long long>& input, vector<complex<double> >& output) const
{
int n = 1;
while(n < (int)input.size())
n *= 2;
vector<complex<double> > x(input.begin(), input.end());
x.resize(n);
for(int h=1; h<n; h*=2){
int w = n / h / 2;
vector<complex<double> > y = x;
for(int k=0; k<h; ++k){
complex<double> omega = polar<double>(1, PI * k / h);
for(int j=0; j<w; ++j){
complex<double> y0 = y[2*w*k+j];
complex<double> y1 = y[2*w*k+j+w] * omega;
x[w*k+j] = y0 + y1;
x[w*(k+h)+j] = y0 - y1;
}
}
}
output.swap(x);
}
void idft(const vector<complex<double> >& input, vector<long long>& output) const
{
int n = 1;
while(n < (int)input.size())
n *= 2;
vector<complex<double> > x(input.begin(), input.end());
x.resize(n);
for(int h=1; h<n; h*=2){
int w = n / h / 2;
vector<complex<double> > y = x;
for(int k=0; k<h; ++k){
complex<double> omega = polar<double>(1, - PI * k / h);
for(int j=0; j<w; ++j){
complex<double> y0 = y[2*w*k+j];
complex<double> y1 = y[2*w*k+j+w] * omega;
x[w*k+j] = y0 + y1;
x[w*(k+h)+j] = y0 - y1;
}
}
}
output.resize(n);
for(int i=0; i<n; ++i){
double tmp = x[i].real() / n;
output[i] = (long long)(tmp + 0.5);
}
}
public:
Bigint(){
sign = true;
}
Bigint(long long x){
sign = (x >= 0);
x = abs(x);
while(x > 0){
a.push_back(x % MAX);
x /= MAX;
}
}
Bigint(const string& s){
sign = true;
long long tmp = MAX;
for(int i=s.size()-1; i>=0; --i){
if(tmp == MAX){
a.push_back(0);
tmp = 1;
}
if('0' <= s[i] && s[i] <= '9'){
a.back() += (s[i] - '0') * tmp;
tmp *= 10;
}
else if(i == 0 && s[0] == '-'){
sign = false;
}
else{
throw(exception());
}
}
normalize();
}
long long getNum() const{
long long ans = 0;
for(int i=a.size()-1; i>=0; --i){
ans *= MAX;
ans += a[i];
}
return ans * (sign? 1:-1);
}
string getStr() const{
ostringstream oss;
if(a.size() == 0)
return "0";
if(!sign)
oss << '-';
for(int i=a.size()-1; i>=0; --i){
oss << a[i];
oss << setw(LEN) << setfill('0');
}
return oss.str();
}
Bigint operator+(const Bigint& x) const{
if(sign ^ x.sign){
Bigint tmp = x;
tmp.sign = !tmp.sign;
return *this - tmp;
}
Bigint ans;
ans.sign = sign;
long long carry = 0;
unsigned i = 0;
while(i < a.size() || i < x.a.size() || carry > 0){
if(i < a.size())
carry += a[i];
if(i < x.a.size())
carry += x.a[i];
ans.a.push_back(carry % MAX);
carry /= MAX;
++ i;
}
return ans;
}
Bigint operator-(const Bigint& x) const{
if(sign ^ x.sign){
Bigint tmp = x;
tmp.sign = !tmp.sign;
return *this + tmp;
}
Bigint ans;
long long carry = 0;
unsigned i=0;
while(i < a.size() || i < x.a.size()){
if(i < a.size())
carry += a[i];
if(i < x.a.size())
carry -= x.a[i];
if(carry < 0){
ans.a.push_back(MAX + carry);
carry = -1;
}
else{
ans.a.push_back(carry);
carry = 0;
}
++ i;
}
if(carry == -1){
ans.sign = !ans.sign;
for(unsigned j=0; j<ans.a.size(); ++j)
ans.a[j] = MAX - ans.a[j] - 1;
++ ans.a[0];
}
ans.normalize();
return ans;
}
Bigint operator*(const Bigint& x) const{
vector<long long> b = a;
vector<long long> c = x.a;
int n = max(b.size(), c.size());
b.resize(n * 2, 0);
c.resize(n * 2, 0);
vector<complex<double> > p, q;
dft(b, p);
dft(c, q);
n = max(p.size(), q.size());
vector<complex<double> > r(n);
for(int i=0; i<n; ++i)
r[i] = p[i] * q[i];
Bigint ans;
ans.sign = !(sign ^ x.sign);
idft(r, ans.a);
long long carry = 0;
for(int i=0; i<n; ++i){
ans.a[i] += carry;
carry = ans.a[i] / MAX;
ans.a[i] %= MAX;
}
if(carry > 0)
ans.a.push_back(carry);
ans.normalize();
return ans;
}
bool operator<(const Bigint& x) const{
if(sign ^ x.sign)
return x.sign;
if(a.size() != x.a.size())
return !(sign ^ (a.size() < x.a.size()));
for(int i=a.size()-1; i>=0; --i){
if(a[i] != x.a[i])
return !(sign ^ (a[i] < x.a[i]));
}
return false;
}
};
Bigint solve(int len)
{
vector<Bigint> dp(len+1, 0);
vector<Bigint> sum(len+1, 0);
dp[0] = 1;
sum[0] = 1;
for(int i=1; i<=len; ++i){
dp[i] = dp[i] + sum[i-1];
sum[i] = dp[i];
if(i >= 2)
sum[i] = sum[i] + sum[i-2];
}
return dp[len];
}
int main()
{
int len;
cin >> len;
if(len == 2){
cout << 3 << endl << "INF" << endl;
return 0;
}
Bigint ans = solve(len);
if(len % 2 == 0){
Bigint x = solve(len / 2);
ans = ans - x * x;
}
cout << len << endl << ans.getStr() << endl;
return 0;
}