suansuansuan
已知数列f：f0=f1=1,fn+1 = fn+fn-1+1(n>=1).
求Sn = ∑i∈[0,n] fik(n<264,k∈[1,13])
k=1时：
构造转移矩阵A：{A0,A1,A2,A3},列向量B：(Sn,fn,fn-1,1),使得AxB=(Sn+1,fn+1,fn,1).
A0 = (1,1,1,1)
A1 = (0,1,1,1)
A2 = (0,1,0,0)
A3 = (0,0,0,1)
k=2时：
构造转移矩阵A：{A0,A1,A2,A3,A4,A5,A6},列向量B：(Sn,fn2,fnfn-1,fn-12,fn,fn-1,1),使得AxB=(Sn+1,fn+12,fn+1fn,fn2,fn+1,fn,1).
A0 = (1,1,2,1,2,2,1)
A1 = (0,1,2,1,2,2,1)
A2 = (0,1,1,0,1,0,0)
A3 = (0,1,0,0,0,0,0)
A4 = (0,0,0,0,1,1,1)
A5 = (0,0,0,0,1,0,0)
A6 = (0,0,0,0,0,0,1)
容易发现我们所用到的项除了Sn之外就只有fnifn-1j(i+j<=k)
并且fn+1afn-1b(a+b<=k)都能用fnifn-1j(i+j<=k)来线性表示.
fn+1afnb = (fn+fn-1+1)afnb
= ∑i∈[0,a] C(a,i)*(fn+fn-1)afnb
= ∑i∈[0,a] C(a,i)*∑j∈[0,i] C(i,j)*fnjfn-1i-jfnb
= ∑i∈[0,a] ∑j∈[0,i] C(a,i)*C(i,j)*fnb-jfn-1i-j
这样就能O(k4)预处理出转移矩阵A
然后就可以用快速幂加速矩阵乘法O(k6logn)求解Sn了
#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#define MAXN 110
#define Mod 1000000000
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<int,int>cp;
inline void set_IO(){
freopen("suansuansuan.in","r",stdin);
freopen("suansuansuan.out","w",stdout);
}
ull n;
int k,C[20][20];
int A[MAXN][MAXN],B[MAXN];
inline void mul(int A[MAXN][MAXN],int B[MAXN][MAXN],int n){
static int C[MAXN][MAXN];
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
C[i][j]=0;
}
for(int i=0;i<=n;++i)
for(int k=0;k<=n;++k){
if(!A[i][k])continue;
for(int j=0;j<=n;++j){
C[i][j]+=(ll)A[i][k]*B[k][j]%Mod;
C[i][j]%=Mod;
}
}
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
A[i][j]=C[i][j];
}
}
inline void qpow(int x[MAXN][MAXN],int n,ull k){
static int ans[MAXN][MAXN];
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
ans[i][j]=bool(i==j);
}
for(;k;mul(x,x,n),k>>=1)
if(k&1)mul(ans,x,n);
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
x[i][j]=ans[i][j];
}
}
map<cp,int>id;
int Id;
int main(){
set_IO();
cin>>n>>k;
if(n<2){
printf("%09d",(int)n+1);
return 0;
}
for(int i=0;i<=k;++i){
C[i][0]=1;
for(int j=1;j<=i;++j){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
}
}
for(int i=k;~i;--i)
for(int j=i;~j;--j){
id[cp(j,i-j)]=++Id;
}
for(int a=0;a<=k;++a)
for(int b=0;a+b<=k;++b){
int x=id[cp(a,b)];
for(int i=0;i<=a;++i)
for(int j=0;j<=i;++j){
int y=id[cp(b+j,i-j)];
A[x][y]=(ll)C[a][i]*C[i][j]%Mod;
}
}
A[0][0]=1;
for(int i=1,x=id[cp(k,0)];i<=Id;++i){
A[0][i]=A[x][i];
}
qpow(A,Id,n-1);
B[0]=2;
for(int i=1;i<=Id;++i){
B[i]=1;
}
int ans=0;
for(int i=0;i<=Id;++i){
ans=(ans+(ll)A[0][i]*B[i]%Mod)%Mod;
}
printf("%09d\n",ans);
return 0;
}
math
求 S(n) = ∑i∈[1,n]∑j∈[1,n] F(i,j),n<=109
F(i,j) = ∑d∈[1,i*j] [d | i*j]
1. 化简S(n)
step 1.
F(i,j) = ∑d∈[1,i*j] [d/gcd(i,d) | i*j/gcd(i,d)]
= ∑d∈[1,i*j] [d/gcd(i,d) | j]
step 2.
S(n) = ∑i∈[1,n]∑j∈[1,n]∑d∈[1,i*j] [d/gcd(i,d) | j]
= ∑i∈[1,n]∑d∈[1,i*n] [n/(d/gcd(i,d)]
= ∑i∈[1,n]∑d∈[1,i*n] [n*gcd(i,d)/d]
step 3.
S(n) = ∑i∈[1,n]∑d∈[1,i*n]∑k [gcd(i,d)==k]*[n*k/d]
= ∑k∑i∈[1,n/k]∑d∈[1,n] [gcd(i,d)==1]*[n/d]
S(n) = ∑i∈[1,n]∑d∈[1,n]∑k∈[1,n/i] [gcd(i,d)==1]*[n/d]
= ∑i∈[1,n]∑d∈[1,n] [gcd(i,d)==1]*[n/d]*[n/i]
S(n) = ∑i∈[1,n]∑j∈[1,n] [gcd(i,j)==1]*[n/i]*[n/j]
step 4.
S(n) = ∑d μ(d)*∑i∈[1,n/d] ∑j∈[1,n/d] [n/(id)]*[n/(jd)]
= ∑d μ(d)*∑i∈[1,n/d] [n/(id)]*∑j∈[1,n/d] [n/(jd)]
令g(n) = ∑i∈[1,n] [n/i],则S(n) = ∑d μ(d)*g([n/d])2
只计算所有不同的[n/d],可以做到O(n2/3)
2.0 计算M(n) = ∑i∈[1,n] μ(i)
M(n) = ∑i∈[1,n] μ(i)
= ∑i∈[1,n] (∑d|i μ(d) - ∑d|i,d<i μ(d))
= 1 - ∑i∈[1,n]∑d|i,d<i μ(d)
= 1 - ∑d|i,d<i∑i∈[1,n] μ(d)
= 1 - ∑d∈[1,n] ∑i∈[2,n/d] μ(d)
= 1 - ∑i∈[2,n] ∑d∈[1,n/i] μ(d)
= 1 - ∑i∈[2,n] M([n/i])
筛出n2/3以内的M，查询的时候查表O(1)回答.
对于大于n2/3的情况，我们用hash表来记忆化.
这样能做到O(n2/3)的复杂度.
2.1 计算F(n) = ∑i∈[1,n] phi(i)
由n = ∑d|n phi(d) ,我们可以类似地得到F(n)的计算方法
F(n) = ∑i∈[1,n] phi(i)
= ∑i∈[1,n] (∑d|i phi(d) - ∑d|i,d<i phi(d))
= n(n+1)/2 - ∑i∈[1,n]∑d|i,d<i phi(d)
= n(n+1)/2 - ∑i∈[2,n] F([n/i])
3. 码码码
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 1000005
#define SIZE ((1<<18)-1)
#define Mod 1000000007
using namespace std;
typedef long long ll;
namespace Mobius{
bool ban[MAXN];
vector<int>p;
int n,mu[MAXN],ptot;
inline void linear_shake(int n){
mu[1]=1;
for(int i=2;i<=n;++i){
if(!ban[i]){
++ptot;
p.push_back(i);
mu[i]=Mod-1;
}
for(int j=0,k;j<ptot;++j){
if((ll)i*p[j]>n)break;
ban[k=i*p[j]]=1;
if(i%p[j]){
mu[k]=Mod-mu[i];
}
else{
mu[k]=0;
break;
}
}
}
for(int i=2;i<=n;++i){
mu[i]=(mu[i]+mu[i-1])%Mod;
}
}
int set[MAXN],f[MAXN];
int head[SIZE+1],tot,next[MAXN];
inline int M(int x){
if(!ptot)linear_shake(n=1000000);
if(x<=n)return mu[x];
int p=x&SIZE;
for(int i=head[p];i;i=next[i])
if(set[i]==x){
return f[i];
}
int res=1;
for(int i=2,j;i<=x;i=j+1){
j=x/(x/i);
res=(res+Mod-ll(j-i+1)*M(x/i)%Mod)%Mod;
}
int o=++tot;
set[o]=x,f[o]=res;
next[o]=head[p],head[p]=o;
return res;
}
};
inline void set_IO(){
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
}
inline int g(int n){
int res=0;
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
res=(res+ll(j-i+1)*(n/i)%Mod)%Mod;
}
return res;
}
int n,ans;
int main(){
set_IO();
scanf("%d",&n);
for(int i=1,j,k;i<=n;i=j+1){
j=n/(n/i);
k=g(n/i),k=(ll)k*k%Mod;
k=(ll)k*((Mobius::M(j)+Mod-Mobius::M(i-1))%Mod)%Mod;
ans=(ans+k)%Mod;
}
printf("%d\n",ans);
return 0;
}
help
求 ∑n∈[1,N]∑m∈[1,M]∑k∈[0,m) [(nk+x)/m] (N,M<=500000,x为实数且x∈[0,100000])
0.首先令x = [x]显然是不影响结果的
1.先考虑如何化简∑k∈[0,m) [(nk+x)/m]
首先显然有：[(nk+x)/m] = [(nk%m+x)/m]+[nk/m]
[(nk+x)/m] = [(nk%m+x)/m]+(nk-nk%m)/m
则∑k∈[0,m) [(nk+x)/m] = ∑k∈[0,m) [(nk%m+x)/m] + ∑k∈[0,m) nk/m + ∑k∈[0,m) nk%m/m
令d=gcd(n,m)，则∑k∈[0,m) [(nk%m+x)/m] = d([x/m]+[(x+d)/m]+...+[(x+m-d)/m])
= d([(x/d)/(m/d)]+[((x/d)+1)/(m/d)]+...+[((x/d)+m/d-1)/(m/d)])
= d([(x/d)(m/d)/(m/d)] (注)
= d[x/d]
∑k∈[0,m) nk%m = d(0+d+...+m-d)
= (m-d)/2
∑k∈[0,m) [(nk+x)/m] = d[x/d]+n(m-1)/2+(d-m)/2
= d[x/d]+(n-1)(m-1)/2+(d-1)/2
由此可见：∑k∈[0,m) [(nk+x)/m] = ∑k∈[0,n) [(mk+x)/n]
注：
对于正整数m和实数x, [mx] = [x] + [x + 1/m] + ... + [x + (m-1)/m]
证明：
x = [x] + {x}
设：k = [m{x}]
则k/m <= m{x} < (k+1)/m
[mx] = [m([x] + {x})]
= m[x] + [m{x}]
= m[x] + k
[x]+[x+1/m]+...+[x+(m-1)/m]
= m[x] + [{x}+1/m] + ... + [{x}+(m-1)/m]
= m[x] + k
[mx] = [x] + [x + 1/m] + ... + [x + (m-1)/m]
2. 再考虑如何计算∑n∈[1,N]∑m∈[1,M] d[x/d]+(n-1)(m-1)/2+(d-1)/2 (d=gcd(n,m))
分为3部分计算：
1) ∑n∈[1,N]∑m∈[1,M] d[x/d]
2) ∑n∈[1,N]∑m∈[1,M] (n-1)(m-1)/2
3) ∑n∈[1,N]∑m∈[1,M] (d-1)/2
1) 和 3) 考虑容斥，枚举d , 再枚举d的倍数，复杂度O(nlogn)
2) 可以直接O(1)计算
3.码码码
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define P 998244353
#define r2 499122177
#define MAXN 500005
using namespace std;
#define g() getchar()
template<class Q>inline void Scan(Q&x){
char c; int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
typedef long long ll;
ll n,m,x;
ll p1,p2,p3;
bool ban[MAXN];
vector<int>p;
int mu[MAXN],tot;
inline void get_mu(int n){
mu[1]=1;
for(int i=2;i<=n;++i){
if(!ban[i]){
++tot;
p.push_back(i);
mu[i]=-1;
}
for(int j=0;j<tot;++j){
if((ll)i*p[j]>n)break;
int x=i*p[j];
ban[x]=1;
if(i%p[j]){
mu[x]=P-mu[i];
}
else{
mu[x]=0;
break;
}
}
}
}
inline void set_IO(){
freopen("help.in","r",stdin);
freopen("help.out","w",stdout);
}
int main(){
set_IO();
Scan(n),Scan(m);
if(n>m)swap(n,m);
get_mu(n);
Scan(x);
p3=(P-n*m%P)%P;
for(int d=1;d<=n;++d)
for(int k=1,D;(D=k*d)<=n;++k){
int a=n/D,b=m/D;
p1=(p1+x/d*d*a%P*b%P*mu[k]%P)%P;
p3=(p3+(ll)d*a%P*b%P*mu[k]%P)%P;
}
p2=((n*(n-1)>>1)%P)*((m*(m-1)>>1)%P)%P;
ll ans=(p1+(p2+p3)*r2%P)%P;
cout<<ans<<endl;
return 0;
}
bzoj2321 星器
定义一个点的势能是i2+j2，求出两个状态的势能之差。。。
我不会证明。
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define inf 0x7f7f7f7f
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
typedef double db;
int n,m;
ll ans;
int main(){
Scan(n),Scan(m);
rep(i,1,n+1)
rep(j,1,m+1){
int x; Scan(x);
ans+=(1ll*i*i+1ll*j*j)*x;
}
rep(i,1,n+1)
rep(j,1,m+1){
int x; Scan(x);
ans-=(1ll*i*i+1ll*j*j)*x;
}
if(ans<0)ans=-ans;
printf("%lld\n",ans>>1);
return 0;
}
bzoj1391 [CEOI2008]knights
every-SG:必胜或必败由步数最长的状态决定。
sg函数和步数打个表找找规律什么的。。。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=2e5+5;
const int d[4][2]={{-2,+1},{-2,-1},{-1,-2},{+1,-2}};
int k,n;
inline bool isMove(int x,int y){
if(x<1||x>n)return 0;
if(y<1||y>n)return 0;
return 1;
}
inline int sg(int x,int y){
if((x%4==1||x%4==2)&&(y%4==1||y%4==2))return 0;
if(n%4==1&&((x==n&&y!=n-1)||(y==n&&x!=n-1)))return 0;
if(n%4==0&&x==n&&y==n)return 0;
return 1;
}
inline int dis(int x,int y){
if(!sg(x,y)){
if(x==n||y==n)return (x+y-2)/4*2;
return (x+y-1)/4*2;
}
int res=0;
for(int i=0;i<4;++i){
int dx=x+d[i][0];
int dy=y+d[i][1];
if(!isMove(dx,dy)||sg(dx,dy))continue;
res=max(res,dis(dx,dy)+1);
}
return res;
}
inline void find(int x,int y){
int l=dis(x,y),s=sg(x,y);
for(int i=0;i<4;++i){
int dx=x+d[i][0];
int dy=y+d[i][1];
if(!isMove(dx,dy)||(s&&sg(dx,dy)))continue;
if(l==dis(dx,dy)+1){
printf("%d %d\n",dx,dy);
return;
}
}
}
int x[MAXN],y[MAXN];
int maxl,ans;
int main(){
freopen("knights.in","r",stdin);
freopen("knights.out","w",stdout);
scanf("%d%d",&k,&n);
for(int i=1;i<=k;++i){
scanf("%d%d",x+i,y+i);
int tmp=dis(x[i],y[i]);
int s=sg(x[i],y[i]);
if(maxl<tmp||(maxl==tmp&&s))
maxl=tmp,ans=s;
}
if(ans){
puts("YES");
for(int i=1;i<=k;++i)
find(x[i],y[i]);
}
else puts("NO");
return 0;
}
Invatation
题意:
有A个男生和B个女生(A,B<=109)。
已知n(n<=105)对朋友关系。
每对关系描述编号在一个区间中的男生和编号在另一个区间中的女生属于一个朋友圈。
每个朋友圈有一个好感度。
现在有个男生C要邀请所有人参加派对。
每个人只能被邀请1次，被同属于一个朋友圈的人邀请会得到对应好感度的奖励。
最大化得到的奖励。
分析:
直接离散化后对线段做kruskal求最大生成树。。。
#include <set>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define l first
#define r second
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;
#define g() getchar()
template<class Q>inline void Scan(Q&x){
char c; int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
const int MAXN=1e5+5;
typedef long long ll;
int A,B,n;
typedef pair<int,int>pr;
pr a[MAXN],b[MAXN];
int cnt,w[MAXN],id[MAXN];
inline bool cmp(int a,int b){
return w[a]>w[b];
}
int ta,ah[MAXN*6],tb,bh[MAXN*6];
int f[MAXN*12],sz[MAXN*12];
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
inline void merge(int x,int y){
if(sz[x]<sz[y])swap(x,y);
sz[y]+=sz[x],f[x]=y;
}
ll ans;
set<int>iru,neko;
inline void Addh(int*a,int&t,int x){
a[++t]=x-1,a[++t]=x,a[++t]=x+1;
}
inline int find(int*a,int n,int x){
return lower_bound(a+1,a+1+n,x)-a;
}
inline void Init(){
Scan(A),Scan(B),Scan(n);
Scan(n);
rep(i,1,n+1){
id[i]=i;
Scan(a[i].l),Scan(a[i].r);
Scan(b[i].l),Scan(b[i].r);
Scan(w[i]);
Addh(ah,ta,a[i].l),Addh(ah,ta,a[i].r);
Addh(bh,tb,b[i].l),Addh(bh,tb,b[i].r);
}
sort(ah+1,ah+1+ta),ta=unique(ah+1,ah+1+ta)-(ah+1);
sort(bh+1,bh+1+tb),tb=unique(bh+1,bh+1+tb)-(bh+1);
rep(i,1,ta+1){
f[i]=i,sz[i]=1;
iru.insert(i);
}
iru.insert(ta+1);
rep(i,1,tb+1){
f[i+ta]=i+ta,sz[i+ta]=1;
neko.insert(i);
}
neko.insert(tb+1);
sort(id+1,id+1+n,cmp);
}
inline void Union(set<int>&s,int*a,int l,int r,int t,int w){
set<int>::iterator it;
while(!s.empty()){
it=s.upper_bound(l);
if(*it>r)return;
int x=find(l+t),y=find(*it+t);
if(x!=y){
int siz=a[*it]-a[*it-1];
cnt+=siz;
ans+=1ll*siz*w;
merge(x,y);
}
s.erase(it);
}
}
inline void Solve(){
rep(cur,1,n+1){
int i=id[cur];
int l1=find(ah,ta,a[i].l),r1=find(ah,ta,a[i].r);
Union(iru,ah,l1,r1,0,w[i]);
int l2=find(bh,tb,b[i].l),r2=find(bh,tb,b[i].r);
Union(neko,bh,l2,r2,ta,w[i]);
int x=find(l1),y=find(l2+ta);
if(x!=y){
++cnt;
ans+=w[i];
merge(x,y);
}
}
printf("%I64d\n",cnt<A+B -1?-1:ans);
}
int main(){
freopen("invitation.in","r",stdin);
freopen("invitation.out","w",stdout);
Init(); Solve(); return 0;
}
kangaroo
题意:
有n(n<=300)只袋鼠，袋鼠i的体积为ai，口袋大小为bi(ai>bi)。
把袋鼠i放入袋鼠j的口袋里。
要求此时袋鼠i和j的口袋里没有袋鼠，且袋鼠i,j不在其它袋鼠口袋里。
不断操作直到不能操作为止，有多少种不同的终止状态，对109+7取模。
分析:
考虑一种合法的终止状态。
一定存在一只袋鼠，比它小的袋鼠都被装了，能装它的袋鼠都装了其它袋鼠。
先将a和b分别排序。
然后枚举这只倒霉的袋鼠i，dp算出方案数。
将a和b都按是否大于ai分成左右两边。
用f[i][j]表示a中左边前i个与b中左边匹配j对的方案数。
用g[i][j]表示b中右边前i个与a中右边匹配j对的方案数。
枚举a中左边与b中右边匹配的对数k，则这k对有k!种匹配方法。
再乘上ab两边分别匹配的方案数，就是所有的方案数。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>inline void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
#define dat(i,a,b) for(int i=a;i>b;--i)
const int MAXN=305;
const int Mod=1e9+7;
int n,ans;
int fac[MAXN];
int f[MAXN][MAXN],g[MAXN][MAXN];
int a[MAXN],b[MAXN];
inline void Init(){
Scan(n);
rep(i,1,n+1){
Scan(a[i]),Scan(b[i]);
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
fac[0]=1;
rep(i,1,n+1)
fac[i]=1ll*fac[i-1]*i%Mod;
}
inline void Solve(){
rep(wuke,1,n+1){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
int r=upper_bound(b+1,b+n+1,a[wuke])-b;
f[0][0]=1;
rep(i,1,r)
rep(j,0,i+1){
f[i][j]=f[i-1][j];
int x=lower_bound(a+1,a+wuke,b[i])-a-1;
if(j&&x-j+1>0){
f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(x-j+1)%Mod)%Mod;
}
}
g[n+1][0]=1;
dat(i,n,wuke)
rep(j,0,n-i+2){
g[i][j]=g[i+1][j];
int x=n-(upper_bound(b+r,b+n+1,a[i])-b)+1;
if(j&&x-j+1>0){
g[i][j]=(g[i][j]+1ll*g[i+1][j-1]*(x-j+1)%Mod)%Mod;
}
}
int s=min(wuke-1,n-r+1);
rep(i,0,s+1){
ans=(ans+1ll*f[r-1][wuke-1-i]*g[wuke+1][n-r+1-i]%Mod*fac[i]%Mod)%Mod;
}
}
printf("%d\n",ans);
}
int main(){
freopen("kangaroo.in","r",stdin);
freopen("kangaroo.out","w",stdout);
Init(); Solve(); return 0;
}
loneliness
题意:
给出一棵以1为根的有向树，每个节点上有一个字符(只会是小写字母)。
多次询问，给出一个字符集合，要求统计树上合法的串的数量。
合法的串满足4个要求:
1.是树上某个点向根方向的走所形成的串
2.串中所有的字符来自给定的字符集合
3.给定的字符集合中的每一个字符都在串中出现过
4.没有被任意一个满足前三条条件的路径完全包含
树的节点数和询问次数均不超过105
分析:
如果一个路径合法的串，当且仅当该路径向两端延伸1个位置都不能有在路径出现的字符。
我们记录每个节点向根方向的最近的出现某个字符的节点，显然合法的串只可能出现在这条路径上。
再记录每个节点所有儿子的字符集合，对于每个节点按深度枚举要走到的字符，判断是否合法。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>inline void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=50005;
const int Alpha=26;
typedef long long ll;
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
e[++tot]=edge(t,head[s]),head[s]=tot;
e[++tot]=edge(s,head[t]),head[t]=tot;
}
char a[MAXN],b[MAXN];
int p[MAXN],dep[MAXN];
int last[MAXN][Alpha];
ll son[MAXN];
void dfs(int x){
rep(i,0,Alpha)
last[x][i]=last[p[x]][i];
last[x][a[p[x]]-'a']=p[x];
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
p[y]=x;
dep[y]=dep[x]+1;
son[x]|=1ll<<(a[y]-'a');
dfs(y);
}
}
int n,m;
int ans[MAXN];
const int SIZE=(1<<18)-1;
struct hash{
ll set[MAXN];
int next[MAXN],id[MAXN];
int head[SIZE+1],tot;
inline void insert(ll s,int Id){
int p=s&SIZE;
set[++tot]=s,next[tot]=head[p];
id[tot]=Id,head[p]=tot;
}
inline void update(ll s){
int p=s&SIZE;
for(int i=head[p];i;i=next[i])
if(set[i]==s)++ans[id[i]];
}
}set;
inline bool cmp(int a,int b){return dep[a]>dep[b];}
inline void deal(int x){
static int q[Alpha+1];
rep(i,0,Alpha)q[i]=last[x][i];
sort(q,q+Alpha,cmp);
ll S=1ll<<(a[x]-'a');
rep(i,0,Alpha){
if(S&son[x])break;
if(!q[i])break;
ll s=1ll<<(a[q[i]]-'a');
if(!(S&s)){
set.update(S);
}
S|=s;
}
if(S&son[x])return;
set.update(S);
}
int main(){
freopen("loneliness.in","r",stdin);
freopen("loneliness.out","w",stdout);
Scan(n),Scan(m);
scanf("%s",a+1);
rep(i,1,n){
int u,v;
Scan(u),Scan(v);
AddEdge(u,v);
}
rep(i,1,m+1){
ll S=0;
scanf("%s",b);
int l=strlen(b);
rep(j,0,l){
S|=1ll<<(b[j]-'a');
}
set.insert(S,i);
}
dep[1]=1,dfs(1);
rep(i,1,n+1)deal(i);
rep(i,1,m+1)printf("%d\n",ans[i]);
return 0;
}
codeforces 455E Function
题意:
f(1, j) = a[j], 1 ≤ j ≤ n.
f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.
多次询问求f(x,y)
分析:
一定存在一种最优解使得a[k]出现x-y+k次，a[i]出现恰好1次(i>k+1&&i<=y).
则在区间[y-x+1,y]找一个k，使得(x-y+k)*a[k]+∑i(i>k+1&&i<=y) a[i]最小
令s为a的前缀和，则式子化为(x-y)*a[k]+k*a[k]+s[y]-s[k]
用线段树维护(a[k],k*a[k]-s[k])的凸包，询问时在凸包上三分。
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>inline void Scan(Q&x){
char c; int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define lch x->l,l,mid
#define rch x->r,mid+1,r
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=1e5+5;
typedef long long ll;
struct poi{
ll x,y;
poi(ll x=0,ll y=0):x(x),y(y){}
inline bool operator<(const poi&o)const{
return x!=o.x?x<o.x:y<o.y;
}
friend poi operator-(const poi&a,const poi&b){
return poi(a.x-b.x,a.y-b.y);
}
friend ll cross(const poi&a,const poi&b){
return a.x*b.y-a.y*b.x;
}
}p[MAXN];
typedef vector<poi>convex;
inline void merge(convex&st,const convex&a,const convex&b){
int s1=a.size(),s2=b.size();
int i1=0,i2=0,top=-1;
while(i1<s1||i2<s2){
poi p=(i2==s2||(i1<s1&&a[i1]<b[i2]))?a[i1++]:b[i2++];
while(top>0&&cross(p-st[top-1],st[top]-st[top-1])>=0)
st.pop_back(),--top;
st.push_back(p),++top;
}
}
typedef struct node*star;
struct node{
convex hull;
star l,r;
inline void update(){
merge(hull,l->hull,r->hull);
}
}pool[MAXN<<2];
star tail=pool;
void build(star&x,int l,int r){
x=tail++;
if(l==r){
x->hull.push_back(p[l]);
return;
}
int mid=(l+r)>>1;
build(lch),build(rch);
x->update();
}
inline ll calc(convex&p,ll a){
int l=0,r=p.size();--r;
while(r-l>2){
int m1=(l+l+r)/3,m2=(l+r+r)/3;
ll a1=p[m1].x*a+p[m1].y;
ll a2=p[m2].x*a+p[m2].y;
if(a1>a2)l=m1;
else r=m2;
}
ll res=1ll<<60;
rep(i,l,r+1){
ll tmp=p[i].x*a+p[i].y;
if(res>tmp)res=tmp;
}
return res;
}
ll a,ans;
ll query(star x,int l,int r,int ll,int rr){
if(l==ll&&r==rr)return calc(x->hull,a);
int mid=(l+r)>>1;
if(rr<=mid)return query(lch,ll,rr);
if(ll>mid) return query(rch,ll,rr);
return min(query(lch,ll,mid),query(rch,mid+1,rr));
}
int n,m;
ll w[MAXN],s[MAXN];
star rt;
inline void Init(){
Scan(n),Scan(m);
rep(i,1,n+1){
Scan(w[i]);
s[i]=s[i-1]+w[i];
p[i]=poi(w[i],w[i]*i-s[i]);
}
build(rt,1,n);
}
inline void Solve(){
rep(i,1,m+1){
int x,y;
Scan(x),Scan(y);
x^=ans,y^=ans;
a=x-y;
ans=query(rt,1,n,y-x+1,y)+s[y];
printf("%I64d\n",ans);
}
}
int main(){
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
Init(); Solve(); return 0;
}
Swap
题意:
给出一个n*m(n<=103,m<=103)的黑白棋棋盘.
棋盘上有t(t<=105)个位置坏掉了。
除了坏掉的位置之外，每个位置上有且只有1颗棋子，且初始时白面向上。
你可以进行k(k<=109)次操作。
每次操作选择两颗棋子，将以它们为对角线的矩形内的所有棋子状态取反(不一定是主对角线).
问k次操作后，白面向上的棋子个数的期望值是多少。
分析:
由于期望具有线性性，我们可以分别计算每颗棋子的期望最后再求和。
假设某颗棋子在1次操作中被翻转的概率为p。
那么容易推出它k次操作后状态不变的概率为(1+(1-2*p)k)/2.
现在问题就在于如何快速求出p.
由容斥得(x,y)被翻转的情况有:
|([1,x]×[1,y],[x,y]×[n,m])|+|([x,n]×[1,y],[1,x]×[y,m])|-|([x,x]×[1,y],[x,x]×[y,m])|-|([1,x]×[y,y],[x,n]×[y,y])|+1
用前缀和优化就好了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=1005;
int n,m,k,t;
bool a[MAXN][MAXN];
int sum[MAXN][MAXN];
inline int Sum(int x1,int y1,int x2,int y2){
int res=sum[x2][y2]-sum[x2][y1-1];
return res-(sum[x1-1][y2]-sum[x1-1][y1-1]);
}
inline void Init(){
Scan(n),Scan(m),Scan(k),Scan(t);
rep(i,1,n+1)rep(j,1,m+1)sum[i][j]=a[i][j]=1;
rep(i,1,t+1){
int x,y;
Scan(x),Scan(y);
sum[x][y]=a[x][y]=0;
}
rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i][j-1];
rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i-1][j];
}
typedef long double ld;
typedef long long ll;
inline ld qpow(ld x,int k){
ld ans=1;
for(;k;x=x*x,k>>=1)
if(k&1)ans=ans*x;
return ans;
}
ld ans;
inline void Solve(){
ll q=1ll*sum[n][m]*sum[n][m];
rep(i,1,n+1)rep(j,1,m+1){
if(!a[i][j])continue;
ll p=1ll*Sum(1,1,i,j)*Sum(i,j,n,m)+1ll*Sum(1,j,i,m)*Sum(i,1,n,j);
p-=1ll*Sum(i,1,i,j)*Sum(i,j,i,m)+1ll*Sum(1,j,i,j)*Sum(i,j,n,j);
p=p<<1|1;
ld pr=(ld)p/q;
ans+=(qpow(1.-pr*2.,k)+1.)/2.;
}
printf("%.20f\n",(double)ans);
}
int main(){
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
Init(); Solve(); return 0;
}
