A.The power of Fibonacci
大致题意：给定n,m,求斐波那契数列前n项m次幂 和.
分析：本来有三种做法，题解做法不会.第一种找循环节.
- 对于线性递推式本来可以根据求通项求得,但是5在1e9下不存在二次剩余.
- 换一种思路,易知在模意义下斐波那契数列的循环节和次幂的循环节是一样的，原数是循环的那这个数的次幂也是循环.
- 但是模数为1e9,如果直接找1e9的循环节,发现循环节大小为1e9+5e8,显然不可行.
- 我们将1e9进行素数拆分成2^9和5^9,两个模数,可以列出关于答案在模512和 1953125 下的同余方程组.{ x===a1%512, y===a2%1953125 }.
- 如何求解a1,a2.我们直接找出512 和 1953125 的最小循环节分别为768,7812500. 暴力存下两个模数的斐波那契数列的m次幂的和.由于前缀和在768和7812500内是重复出现的，我们只用开一个数组进行存储,暴力到7812500即可.
a1=(n/768*sum[n%768]+sum[n%768])mod , a2=(n/7812500 * sum[n%7812500]+sum[n%7812500])%mod . - 最后套用CRT求得答案.
#include<bits/stdc++.h>
typedef long long ll;
const ll p=1e9;
const ll p1=512,loop1=768;
const ll p2=1953125,loop2=7812500;
ll qpow( ll a,ll b ,ll p )
{
ll ans=1;
while( b )
{
if( b&1 ) ans=ans*a%p;
b>>=1;
a=a*a%p;
}
return ans;
}
struct node{
void exgcd( ll a1,ll b,ll &x,ll &y )
{
if( b==0 )
{
x=1;y=0;
return;
}
exgcd(b,a1%b,x,y);
ll tmp=x;
x=y;
y=tmp-(a1/b)*y;
}
ll solve( ll a[], ll m[],int n )
{
ll M=1,ans=0,t,x,y;
for( int i=0;i<n;i++ ) M*=m[i];
for( int i=0;i<n;i++ )
{
t=M/m[i];
exgcd(t,m[i],x,y);
ans=(ans+a[i]*x*t)%M; // 数据比较变态的时候用快速乘
}
ans=(ans+M)%M;
return ans;
}
}CRT;
ll sum[loop2+5],f[loop2+5];
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
f[0]=0,f[1]=sum[1]=1;
for( int i=2;i<loop2+5;i++ )
{
f[i]=f[i-1]+f[i-2];
if( f[i]>=p ) f[i]-=p;
sum[i]=sum[i-1]+qpow(f[i],m,p);
if( sum[i]>=p ) sum[i]-=p;
}
ll a[2],m1[2]={p1,p2};
a[0]=( (n/loop1)*sum[loop1]+sum[n%loop1] )%p;
a[1]=( (n/loop2)*sum[loop2]+sum[n%loop2] )%p;
printf("%lld\n",CRT.solve(a,m1,2) );
}方法二：线性递推式,极其好用的EX_杜教BM.
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#else
#define debug(...)
#endif
// given first m items init[0..m-1] and coefficents trans[0..m-1] or
// given first 2 *m items init[0..2m-1], it will compute trans[0..m-1]
// for you. trans[0..m] should be given as that
// init[m] = sum_{i=0}^{m-1} init[i] * trans[i]
struct LinearRecurrence
{
using int64 = long long;
using vec = std::vector<int64>;
static void extand(vec& a, size_t d, int64 value = 0)
{
if (d <= a.size()) return;
a.resize(d, value);
}
static vec BerlekampMassey(const vec& s, int64 mod)
{
std::function<int64(int64)> inverse = [&](int64 a) {
return a == 1 ? 1 : (int64)(mod - mod / a) * inverse(mod % a) % mod;
};
vec A = { 1 }, B = { 1 };
int64 b = s[0];
for (size_t i = 1, m = 1; i < s.size(); ++i, m++)
{
int64 d = 0;
for (size_t j = 0; j < A.size(); ++j)
{
d += A[j] * s[i - j] % mod;
}
if (!(d %= mod)) continue;
if (2 * (A.size() - 1) <= i)
{
auto temp = A;
extand(A, B.si***t64 coef = d * inverse(b) % mod;
for (size_t j = 0; j < B.size(); ++j)
{
A[j + m] -= coef * B[j] % mod;
if (A[j + m] < 0) A[j + m] += mod;
}
B = temp, b = d, m = 0;
}
else
{
extand(A, B.si***t64 coef = d * inverse(b) % mod;
for (size_t j = 0; j < B.size(); ++j)
{
A[j + m] -= coef * B[j] % mod;
if (A[j + m] < 0) A[j + m] += mod;
}
}
}
return A;
}
static void exgcd(int64 a, int64 b, int64& g, int64& x, int64& y)
{
if (!b)
x = 1, y = 0, g = a;
else
{
exgcd(b, a % b, g, y, x);
y -= x * (a / b);
}
}
static int64 crt(const vec& c, const vec& m)
{
int n = c.size();
int64 M = 1, ans = 0;
for (int i = 0; i < n; ++i) M *= m[i];
for (int i = 0; i < n; ++i)
{
int64 x, y, g, tm = M / m[i];
exgcd(tm, m[i], g, x, y);
ans = (ans + tm * x * c[i] % M) % M;
}
return (ans + M) % M;
}
static vec ReedsSloane(const vec& s, int64 mod)
{
auto inverse = [](int64 a, int64 m) {
int64 d, x, y;
exgcd(a, m, d, x, y);
return d == 1 ? (x % m + m) % m : -1;
};
auto L = [](const vec& a, const vec& b) {
int da = (a.size() > 1 || (a.size() == 1 && a[0])) ? a.size() - 1 : -1000;
int db = (b.size() > 1 || (b.size() == 1 && b[0])) ? b.size() - 1 : -1000;
return std::max(da, db + 1);
};
auto prime_power = [&](const vec& s, int64 mod, int64 p, int64 e) {
// linear feedback shift register mod p^e, p is prime
std::vector<vec> a(e), b(e), an(e), bn(e), ao(e), bo(e);
vec t(e), u(e), r(e), to(e, 1), uo(e), pw(e + 1);
;
pw[0] = 1;
for (int i = pw[0] = 1; i <= e; ++i) pw[i] = pw[i - 1] * p;
for (int64 i = 0; i < e; ++i)
{
a[i] = { pw[i] }, an[i] = { pw[i] };
b[i] = { 0 }, bn[i] = { s[0] * pw[i] % mod };
t[i] = s[0] * pw[i] % mod;
if (t[i] == 0)
{
t[i] = 1, u[i] = e;
}
else
{
for (u[i] = 0; t[i] % p == 0; t[i] /= p, ++u[i])
;
}
}
for (size_t k = 1; k < s.size(); ++k)
{
for (int g = 0; g < e; ++g)
{
if (L(an[g], bn[g]) > L(a[g], b[g]))
{
ao[g] = a[e - 1 - u[g]];
bo[g] = b[e - 1 - u[g]];
to[g] = t[e - 1 - u[g]];
uo[g] = u[e - 1 - u[g]];
r[g] = k - 1;
}
}
a = an, b = bn;
for (int o = 0; o < e; ++o)
{
int64 d = 0;
for (size_t i = 0; i < a[o].size() && i <= k; ++i)
{
d = (d + a[o][i] * s[k - i]) % mod;
}
if (d == 0)
{
t[o] = 1, u[o] = e;
}
else
{
for (u[o] = 0, t[o] = d; t[o] % p == 0; t[o] /= p, ++u[o])
;
int g = e - 1 - u[o];
if (L(a[g], b[g]) == 0)
{
extand(bn[o], k + 1);
bn[o][k] = (bn[o][k] + d) % mod;
}
else
{
int64 coef = t[o] * inverse(to[g], mod) % mod * pw[u[o] - uo[g]] % mod;
int m = k - r[g];
extand(an[o], ao[g].size() + m);
extand(bn[o], bo[g].size() + m);
for (size_t i = 0; i < ao[g].size(); ++i)
{
an[o][i + m] -= coef * ao[g][i] % mod;
if (an[o][i + m] < 0) an[o][i + m] += mod;
}
while (an[o].size() && an[o].back() == 0) an[o].pop_back();
for (size_t i = 0; i < bo[g].size(); ++i)
{
bn[o][i + m] -= coef * bo[g][i] % mod;
if (bn[o][i + m] < 0) bn[o][i + m] -= mod;
}
while (bn[o].size() && bn[o].back() == 0) bn[o].pop_back();
}
}
}
}
return std::make_pair(an[0], bn[0]);
};
std::vector<std::tuple<int64, int64, int>> fac;
for (int64 i = 2; i * i <= mod; ++i)
{
if (mod % i == 0)
{
int64 cnt = 0, pw = 1;
while (mod % i == 0) mod /= i, ++cnt, pw *= i;
fac.emplace_back(pw, i, cnt);
}
}
if (mod > 1) fac.emplace_back(mod, mod, 1);
std::vector<vec> as;
size_t n = 0;
for (auto&& x : fac)
{
int64 mod, p, e;
vec a, b;
std::tie(mod, p, e) = x;
auto ss = s;
for (auto&& x : ss) x %= mod;
std::tie(a, b) = prime_power(ss, mod, p, e);
as.emplace_back(a);
n = std::max(n, a.size());
}
vec a(n), c(as.size()), m(as.size());
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < as.size(); ++j)
{
m[j] = std::get<0>(fac[j]);
c[j] = i < as[j].size() ? as[j][i] : 0;
}
a[i] = crt(c, m);
}
return a;
}
LinearRecurrence(const vec& s, const vec& c, int64 mod) : init(s), trans(c), mod(mod), m(s.size()) {}
LinearRecurrence(const vec& s, int64 mod, bool is_prime = true) : mod(mod)
{
vec A;
if (is_prime)
A = BerlekampMassey(s, mod);
else
A = ReedsSloane(s, mod);
if (A.empty()) A = { 0 };
m = A.size() - 1;
trans.resize(m);
for (int i = 0; i < m; ++i)
{
trans[i] = (mod - A[i + 1]) % mod;
}
std::reverse(trans.begin(), trans.end());
init = { s.begin(), s.begin() + m };
}
int64 calc(int64 n)
{
if (mod == 1) return 0;
if (n < m) return init[n];
vec v(m), u(m << 1);
int msk = !!n;
for (int64 m = n; m > 1; m >>= 1) msk <<= 1;
v[0] = 1 % mod;
for (int x = 0; msk; msk >>= 1, x <<= 1)
{
std::fill_n(u.begin(), m * 2, 0);
x |= !!(n & msk);
if (x < m)
u[x] = 1 % mod;
else
{ // can be optimized by fft/ntt
for (int i = 0; i < m; ++i)
{
for (int j = 0, t = i + (x & 1); j < m; ++j, ++t)
{
u[t] = (u[t] + v[i] * v[j]) % mod;
}
}
for (int i = m * 2 - 1; i >= m; --i)
{
for (int j = 0, t = i - m; j < m; ++j, ++t)
{
u[t] = (u[t] + trans[j] * u[i]) % mod;
}
}
}
v = { u.begin(), u.begin() + m };
}
int64 ret = 0;
for (int i = 0; i < m; ++i)
{
ret = (ret + v[i] * init[i]) % mod;
}
return ret;
}
vec init, trans;
int64 mod;
int m;
};
const int mod = 1e9;
typedef long long ll;
ll Pow(ll a, ll n, ll mod)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= mod)
if (n & 1) (t *= a) %= mod;
return t;
}
int main()
{
int n, m;
cin >> n >> m;
std::vector<long long> f = { 0, 1 };
//预处理 2*m+5项
for (int i = 2; i < m * 2; i++)
f.push_back((f[i - 1] + f[i - 2]) % mod);
for (auto& t : f) t = Pow(t, m, mod);
for (int i = 1; i < m * 2; i++)
f[i] = (f[i - 1] + f[i]) % mod;
LinearRecurrence solver(f, mod, false);
printf("%lld\n", solver.calc(n));
}
D. Knapsack Cryptosystem
大致题意：给定n个物品，问是否能选择哪些物品可以使得重量总和为s.( n<=36 , s<=9e18 , ai<2e17 )
分析:36件物品,折半搜索，二进制枚举，双指针遍历进行check.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>L,R;
vector< pair<ll,ll> >Ls,Rs;
ll a[40],s;
int n;
void enu( vector<ll> A, vector< pair<ll,ll> > &As )
{
int num=A.size();
for( int i=0;i<1ll<<num;i++ )
{
ll sum=0;
for( int j=0;j<num;j++ )
{
if( i>>j & 1 ) sum+=A[j];
}
As.push_back( make_pair(sum,i) );
}
sort( As.begin(),As.end() );
}
ll work()
{
int l=0,r=Rs.size()-1;
while( l<Ls.size() && r>=0 )
{
if( Ls[l].first+Rs[r].first<s ) l++;
else if( Ls[l].first+Rs[r].first>s ) r--;
else
{
return Rs[r].second<<L.size() | Ls[l].second;
}
}
}
int main()
{
scanf("%d%lld",&n,&s);
for( int i=0;i<n;i++ )
{
scanf("%lld",&a[i]);
if( i<n/2 ) L.push_back( a[i] );
else R.push_back( a[i] );
}
enu(L,Ls);
enu(R,Rs);
ll ans=work();
for( int i=0;i<n;i++ ) printf("%d", (int)( ans>>i & 1 ) );
puts("");
} E. All men are brothers
大致题意：n个人,m个朋友关系,对于每一个朋友关系确立后,输出四元组的个数. 四元组定义:两两不是朋友,元素顺序无关. 朋友关系可传递.
分析：
- 在没有任何朋友关系前，答案应该是C(n,4).
- 那么对于确立一个(a1,b1)新关系,我们计算对之前答案的影响.减少的四元组(a,b,c,d) ,a表示 a1 朋友集合的元素,b表示 b1 朋友集合的元素,我们可以确定c,d一定与a,b不是朋友(不然之前就已经减去).c和d也不是朋友.
- 那么这个问题就转换为,我们依据朋友关系进行并查集,对于a的朋友集合,b的朋友集合,和其他的朋友集合中,四元组在a集合选一个元素，b集合选一个元素,再在其他朋友集合中选两个互不为朋友的集合元素.
- 那么如何算其他朋友集合中选两个互不为朋友的集合元素的方案数呢.假设其他集合元素个数是e,f,g;我们要求的是
e * f + e * f + f * g
这个式子可以根据 ( (e+f+g)^2-(e^2+f^2+g^2) )/2 求得. 那么我们只用维护其他集合元素个数之和,和其他集合元素个数平方之和,就能算得答案.
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=1e5+10;
int f[maxn];
ll siz[maxn];
int get_fa( int x ) { return f[x]==x ? x : f[x]=get_fa(f[x]); }
int main()
{
int n,m;
scanf("%d%d",&n,&m);
ll ans=0;
if( n>=4 ) ans=(__int128)n*(n-1)*(n-2)*(n-3)/24;
printf("%lld\n",ans);
ll tmp=n;
for( int i=1;i<=n;i++ ) f[i]=i,siz[i]=1;
while( m-- )
{
int x,y;
scanf("%d%d",&x,&y);
x=get_fa(x);
y=get_fa(y);
if( x!=y )
{
ll nn=n-siz[x]-siz[y];
tmp-=siz[x]*siz[x]+siz[y]*siz[y];
ans-=siz[x]*siz[y]*(nn*nn-tmp )/2;
siz[x]+=siz[y];
f[y]=x;
tmp+=siz[x]*siz[x];
}
printf("%lld\n",ans);
}
} H.Cutting Bamboos
大致题意：给定n棵竹子的高度,有q次操作(L,R,x,y).(n<=2e5,q<=1e5, x,y<=1e9 , l,r<=n ,hi<=1e5 )
操作: L R x y [L,R] 区间内的竹子,每次指定一个高度进行横砍一刀(所有高于该高度的竹子变成该高度),一共横砍y刀使得区间内所有竹子高度变为零,问横砍第x刀时指定的高度是多少.
分析：
- 我们可以求出第x刀后，区间内剩余竹子总高度.那么求第x刀切的高度就是求最后区间竹子的最高高度.
- 先用主席树处理出区间内元素,每个竹子的高度在1e5整数内,直接以高度为key值索引存储，然后根据二叉树结构进行二分check最高高度即可.
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
const int maxn=2e5+10;
struct node{
int l,r,num;
long double sum;
}t[maxn*30];
int root[maxn*30],cnt;
void insert( int l,int r,int pre,int &now,int p )
{
t[++cnt]=t[pre];
now=cnt;
t[now].num++;
t[now].sum+=p;
if( l==r ) return;
int mid=l+r>>1;
if( p<=mid ) insert(l,mid,t[pre].l,t[now].l,p);
else insert(mid+1,r,t[pre].r,t[now].r,p);
}
long double query( int l,int r,int L,int R,long double k,int nu ) //k为剩余的竹子的总量，nu为大于当前节点的数量
{
if( l==r )
{
int num1=t[R].num-t[L].num+nu;
if( num1==0 ) return k;
return k/num1;
}
int mid=l+r>>1;
long double p=t[t[R].l].sum-t[t[L].l].sum; // 左边竹子高度总和
long long q=t[t[R].r].num-t[t[L].r].num; // 右边 竹子个数
long double temp=(long double) ( q+nu )*mid; // 确定mid为最大值进行 判断
if( p+temp>=k ) return query( l,mid,t[L].l,t[R].l,k,nu+q );
else return query( mid+1,r,t[L].r,t[R].r,k-p,nu );
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for( int i=1;i<=n;i++ )
{
int x;scanf("%d",&x);
insert(1,mx,root[i-1],root[i],x);
}
while( m-- )
{
int L,R,x,y;
scanf("%d%d%d%d",&L,&R,&x,&y);
long double sum= t[root[R]].sum-t[root[L-1]].sum;
long double s=sum*(y-x)/y; // 应该剩余的竹子的数量
printf("%.15Lf\n",query(1,mx,root[L-1],root[R],s,0) );
}
} J. Symmetrical Painting
大致题意：给定n个连续分布在坐标轴上黑色矩形的上下边界,把一些黑色矩形涂白，求出剩下有水平对称轴的黑色矩形的最大面积。
分析:
- 先考虑对称轴会在哪些地方产生-----三个地方，某个矩形的上边界、下边界和中间位置.所以我们枚举3*n个位置进行check更新就可以了。
- 考虑如何得到每个位置的黑色矩形面积，对于对称轴从一个矩形下边界移动到上边界的过程，黑色矩形的面积是先增加后减少，那么我们可以用一个标记来记录该矩形面积变化，在下边界打上1，中间位置打上-2，上边界打上1.然后排序，从小到大枚举，利用前缀和当前位置的矩形面积。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
vector< pair<int,int> > p;
int main()
{
int n;
scanf("%d",&n);
for( int i=0;i<n;i++ )
{
ll l,r;
scanf("%lld%lld",&l,&r);
l<<=1;
r<<=1;
p.push_back( make_pair(l,1) );
p.push_back( make_pair(l+r>>1,-2) );
p.push_back( make_pair(r,1) );
}
sort(p.begin(),p.end());
ll ans=0,ma=0,tmp=0,pre=0,a,b;
for( int i=0;i<p.size()-1;i++ )
{
a=p[i].first,b=p[i].second;
pre+=p[i].second;
tmp=p[i+1].first-p[i].first;
ma+=pre*tmp;
ans=max( ans, ma );
}
printf("%lld\n",ans);
}
京公网安备 11010502036488号