題意：f(1)=”a”，f(2)=”b”，f(i)=f(i-1)+f(i-2)，”+”表示連接配接符。給定n,m，求f(n)的前m個字元的“next值”。
分析：打表找到第一個i使M+1<|f(i)| ，答案為 m-|f(i-2)| % MOD
高精度 網上找了一個模闆。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <sstream>
#include <functional>
#include <algorithm>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define memc(a,b) memcpy(a,b,sizeof(b))
#define rep(i,a,n) for(int i=a;i<n;i++) ///[a,n)
#define dec(i,n,a) for(int i=n;i>=a;i--)///[n,a]
#define pb push_back
#define fi first
#define se second
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-);
const double eps=;
const double e=;
const int INF=;
const int MOD=;
const int N=+;
const ll maxn=;
const int dir[][]= {-,,,,,-,,};
struct Biginteger
{
const static int base=;
const static int len=;
typedef vector<int>vec;
typedef long long ll;
vec num;
bool sign;///正負标記 ,1 為負 0為正
Biginteger()
{
num.clear(),sign=;
}
Biginteger(int x)
{
sign=;
if(x<)
{
sign=;
x=-x;
}
num.push_back(x%base);
if(x >= base) num.push_back(x/base);
}
Biginteger(bool s,vec x)
{
sign=s;
num=x;
}
///将一個字元串類型轉化為大數
Biginteger(char *s)
{
int len = strlen(s),x = ,sum = ,f = (s[]=='-');
sign = f;
for(int i=len-; i>=f; i--)
{
sum += (s[i]-'0')*x;
x *= ;
if(x == || i == f)
{
num.push_back(sum);
sum = ;
x=;
}
}
while(num.back() == && num.size() > )
num.pop_back();
}
///添加元素
void push(int x)
{
num.push_back(x);
}
///求絕對值
Biginteger abs()const
{
return Biginteger(false,num);
}
///比較大小
bool smaller(const vec& a,const vec& b)const
{
if(a.size() != b.size()) return a.size() < b.size();
for(int i = a.size()-; i >= ; i--)
{
if(a[i] != b[i])
return a[i] < b[i];
}
return false;
}
bool operator < (const Biginteger &m) const
{
if (sign && !m.sign) return true;
if (!sign && m.sign) return false;
if (sign && m.sign) return smaller(m.num, num);
return smaller(num, m.num);
}
///兩個大數的 大小比較
bool operator > (const Biginteger& m)const
{
return m < *this;
}
///兩個大數 是否相等
bool operator == (const Biginteger& m)const
{
return !(m < *this) && !(*this < m);
}
bool operator >= (const Biginteger& m)const
{
return !(*this < m);
}
bool operator <= (const Biginteger& m)const
{
return !(*this > m);
}
///大數相加 a+b
vec add(const vec& a,const vec& b)const
{
vec ans;
ans.clear();
int x=;
for(int i=; i<a.size(); i++)
{
x += a[i];
if(i < b.size()) x += b[i];
ans.push_back(x % base);
x /= base;
}
for(int i=a.size(); i<b.size(); i++)
{
x += b[i];
ans.push_back(x % base);
x /= base;
}
if(x) ans.push_back(x);
while(ans.back() == && ans.size() > )
ans.pop_back();
return ans;
}
///大數相減
vec sub(const vec& a,const vec& b) const
{
vec ans;
ans.clear();
int x=;
for(int i=; i<b.size(); i++)
{
x += base+a[i]-b[i]-;
ans.push_back(x % base);
x /= base;
}
for(int i=b.size(); i<a.size(); i++)
{
x += base+a[i]-;
ans.push_back(x % base);
x /= base;
}
while(ans.back() == && ans.size() > )
ans.pop_back();
return ans;
}
///大數乘法
vec mul(const vec &a, const vec &b) const
{
vec ans;
ans.resize(a.size() + b.size());
for (int i = ; i < a.size(); i++)
{
for (int j = ; j < b.size(); j++)
{
ll tmp = (ll)a[i] * b[j] + ans[i + j];
ans[i + j + ] += tmp / base;
ans[i + j] = tmp % base;
}
}
while (ans.back() == && ans.size() > )
ans.pop_back();
return ans;
}
///大數除法
vec div(const vec &a, const vec &b) const
{
vec ans(a.size()), x(, ), y(, ), z(, ), t(, );
y.push_back();
for (int i = a.size() - ; i >= ; i--)
{
z[] = a[i];
x = add(mul(x, y), z);
if (smaller(x, b)) continue;
int l = , r = base - ;
while (l < r)
{
int m = (l + r + ) >> ;
t[] = m;
if (smaller(x, mul(b, t))) r = m - ;
else l = m;
}
ans[i] = l;
t[] = l;
x = sub(x, mul(b, t));
}
while (ans.back() == && ans.size() > )
ans.pop_back();
return ans;
}
///重載 加法運算符 兩個大數相加
Biginteger operator + (const Biginteger &m) const
{
if (!sign && !m.sign) return Biginteger(false, add(num, m.num));
if (!sign && m.sign)
{
return *this >= m.abs() ?
Biginteger(false, sub(num, m.num)) : Biginteger(true, sub(m.num, num));
}
if (sign && !m.sign)
{
return (*this).abs() > m ?
Biginteger(true, sub(num, m.num)) : Biginteger(false, sub(m.num, num));
}
return Biginteger(true, add(num, m.num));
}
///重載 減法運算符
Biginteger operator - (const Biginteger &m) const
{
return *this + Biginteger(!m.sign, m.num);
}
///重載 乘法運算符
Biginteger operator * (const Biginteger &m) const
{
Biginteger res(sign ^ m.sign, mul(num, m.num));
if (res.sign && res.num.size() == && res.num[] == )
res.sign = false;
return res;
}
///重載 除法運算符
Biginteger operator / (const Biginteger &m) const
{
if (m == Biginteger()) return m;
Biginteger res(sign ^ m.sign, div(num, m.num));
if (res.sign && res.num.size() == && res.num[] == )
res.sign = false;
return res;
}
///重載 取模運算符
Biginteger operator % (const Biginteger &m) const
{
return *this - *this / m * m;
}
void out() const
{
if(sign) putchar('-');
int size = num.size();
printf("%d",num[size-]);
for(int i=size-; i>=; i--)
printf("%08d",num[i]);
puts("");
}
};
Biginteger f[N+];
char s[N];
void init()
{
f[]=,f[]=f[]=;
for(int i=;i<=N;i++) f[i]=f[i-]+f[i-];
}
int main()
{
init();
//for(int i=1;i<10;i++)f[i].out();
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s);
Biginteger buf(s);
int mid,lb=,ub=N;
while(lb<ub)
{
mid=(lb+ub)>>;
if(f[mid]>buf+) ub=mid;
else lb=mid+;
}
((buf-f[lb-])%MOD).out();
}
return ;
}
![處理PCX檔案[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)