挂分大赛！！！！
20（-80）+100（？？）+60
T1：水，类似容斥，但大样例太水了，2^k-1没乘都能过？？
//100pts
#include
using namespace std;
long long n,m,jc[16];
unsigned long long ans,x[16];
void sd(int k,int id,unsigned long long sum,int num)
{
//if(k==m&&id<=2&&num<=2&&id==num)cout<<sum<n/x[k])
{
sd(k,id,n+1,num+1);
}
else
{
sum=sum*x[k];
sd(k,id,sum,num+1);
}
}
return ;
}
int main()
{
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
jc[0]=1;
for(int i=1;i<=15;i++) jc[i]=jc[i-1]*2;
scanf("%lld%lld",&n,&m);
for(int i=1;i>x[i];
ans+=n/x[i];
}
for(int i=2;i<=m;i++)
{
//cout<<ans<<endl;
sd(0,i,0,0);
}
cout<<ans;
return 0;
}
T2：MQ能过？？
//60pts
#include
using namespace std;
int n,m,q,u[2000005],v[200005],head[2005],nex[200005],L,R,s,t,dp[1005];
int main() {
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
cin>>n>>m>>q;
for(int i=1; i<=m; i++) {
scanf("%d%d",&u[i],&v[i]);
v[i+m]=u[i];
u[i+m]=v[i];
}
while(q--) {
scanf("%d%d%d%d",&L,&R,&s,&t);
for(int i=1; i<=n; i++) dp[i]=0;
dp[s]=1;
for(int i=L; i<=R; i++) {
if(dp[u[i]]==1||dp[v[i]]==1) {
dp[u[i]]=dp[v[i]]=1;
}
}
if(dp[t]==1) {
printf("Yes\n");
} else printf("No\n");
}
return 0;
}
T3：扫描线，先dfn，差分，对于一个操作，把两个起点都加上对应区间，终点之后都减掉
每次查询即查询覆盖
记录一种很新的线段树：思路：标记永久化，不用下传
类似李超树（？），每一个区间的cnt表示能拆分成几个当前区间，序列总和就为每一个区间*cnt还原出来，跟正常线段树差别就在子节点和父节点的信息相对独立
算答案就类似树形dp，由子节点贡献和本身贡献相加
//60pts
#include
using namespace std;
int n,m,uu,vv,aa,bb,fa[100005],ans[100005],cnt,dfn[100005],size[100005],la,ra,lb,rb,tt[100005];
vector G[100005],kl[100005],kr[100005],kd[100005];
struct sd
{
int l,r,sum,len;
}tr[800005];
void build(int pos,int l,int r)
{
tr[pos].l=l;
tr[pos].r=r;
if(l==r) return ;
build(pos*2,l,(l+r)/2);
build(pos*2+1,(l+r)/2+1,r);
}
void dfs(int x,int f)
{
cnt++;
tt[cnt]=x;
dfn[x]=cnt;
fa[x]=f;
size[x]=1;
for(int i=0;i=1)
{
tr[id].len=tr[id].r-tr[id].l+1;
}
else
{
tr[id].len=tr[id*2].len+tr[id*2+1].len;
}
}
void update(int l,int r,int sum,int id)
{
if(tr[id].rr) return ;
if(tr[id].l>=l&&tr[id].r>n>>m;
build(1,1,n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&uu,&vv);
G[uu].push_back(vv);
G[vv].push_back(uu);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&aa,&bb);
la=dfn[aa],ra=dfn[aa]+size[aa]-1;
lb=dfn[bb],rb=dfn[bb]+size[bb]-1;
add(la,la,ra,1);
add(la,lb,rb,1);
add(lb,la,ra,1);
add(lb,lb,rb,1);
//////////////////////////////////////////////
add(ra+1,la,ra,-1);
add(ra+1,lb,rb,-1);
add(rb+1,la,ra,-1);
add(rb+1,lb,rb,-1);
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<": "<<dfn[i]<<endl;
// }
for(int x=1;x<=n;x++)
{
// cout<<x<<":"<<endl;
for(int i=0;i<kl[x].size();i++)
{
update(kl[x][i],kr[x][i],kd[x][i],1);
// cout<<kl[x][i]<<" "<<kr[x][i]<<" "<<kd[x][i]<<endl;
}
ans[tt[x]]=tr[1].len-1;
//cout<<"####"<<endl;
}
for(int i=1;i<=n;i++)
{
cout<<max(0,ans[i])<<" ";
}
return 0;
}
T4：推式子加矩阵快速幂优化，还没过，可能炸long long了
难推
还要换根dp预处理
//48pts
#include
using namespace std;
const unsigned long long mod=1e9+7;
unsigned long long D,ans;
vector G[200005];
long long uu,vv;
unsigned long long n,dp[200005],deep[200005],op,siz[200005],R[200005],su0[200005],rs[200005][2],c,R2[200005],dp2[200005];
void dfs1(long long x,long long f) {
for(long long i=0; i0);
if(su0[x]==1) R[x]=rs[x][0];
else if(su0[x]==0) R[x]=rs[x][1]+1;
}
void dfs2(long long u,long long f) {
//cout<<"1";
long long v;
R2[u]=R[u],dp2[u]=dp[u];
if(dp2[u]==0) c++;
for(long long i=0; i<G[u].size(); i++) {
v=G[u][i];
// cout<<u<<" "<<v<0);
rs[u][dp[v]]-=R[v];
if(su0[u]==1) R[u]=rs[u][0];
else if(su0[u]==0) R[u]=rs[u][1]+1;
else R[u]=0;
su0[v]+=(dp[u]==0);
dp[v]=(su0[v]>0);
rs[v][dp[u]]+=R[u];
if(su0[v]==1) R[v]=rs[v][0];
else if(su0[v]==0) R[v]=rs[v][1]+1;
else R[v]=0;
dfs2(v,u);
su0[u]=s0u,dp[u]=dpu,R[u]=Ru,rs[u][0]=rsu0,rs[u][1]=rsu1;
su0[v]=s0v,dp[v]=dpv,R[v]=Rv,rs[v][0]=rsv0,rs[v][1]=rsv1;
}
}
return ;
}
unsigned long long T[2][2],oh[2][2],ls[2][2],ls2[2][2];
void ksm(long long qwq) {
ls[0][0]=ls[1][1]=1;
ls[1][0]=ls[0][1]=0;
while(qwq>0) {
if(qwq%2==1) {
for(long long i=0; i<=1; i++) {
for(long long j=0; j<=1; j++) {
ls2[i][j]=0;
for(long long k=0; k<=1; k++) {
ls2[i][j]+=ls[i][k]*T[k][j]%mod;
ls2[i][j]%=mod;
}
}
}
for(long long i=0; i<=1; i++) for(long long j=0; j<=1; j++) ls[i][j]=ls2[i][j];
}
qwq/=2;
for(long long i=0; i<=1; i++) {
for(long long j=0; j<=1; j++) {
ls2[i][j]=0;
for(long long k=0; k<=1; k++) {
ls2[i][j]+=T[i][k]*T[k][j]%mod;
ls2[i][j]%=mod;
}
}
}
for(long long i=0; i<=1; i++) for(long long j=0; j>n>>D;
for(long long i=1; i<=n-1; i++) {
scanf("%lld%lld",&uu,&vv);
G[uu].push_back(vv);
G[vv].push_back(uu);
}
dfs1(1,0);
dfs2(1,0);
// for(int i=1;i<=n;i++)
// {
// cout<<dp2[i]<<" "<<R[i]<<endl;
// }
// cout<<"1"<<endl;
//cout<<c<<endl;
oh[0][0]=c,oh[0][1]=n-c;
for(long long i=1; i<=n; i++) {
if(dp2[i]==0) {
T[0][0]+=n-R2[i];
T[0][1]+=R2[i];
T[1][0]+=n;
} else {
T[0][1]+=n-R2[i];
T[0][0]+=R2[i];
T[1][1]+=n;
}
}
//cout<<T[0][0]<<" "<<T[0][1]<<endl<<T[1][0]<<" "<<T[1][1]<<endl;
ksm(D-1);
for(long long i=0; i<=1; i++) {
for(long long j=0; j<=1; j++) {
ls2[i][j]=0;
for(long long k=0; k<=1; k++) {
ls2[i][j]+=ls[i][k]*oh[k][j]%mod;
ls2[i][j]%=mod;
}
}
}
unsigned long long f0=ls2[0][0],f1=ls2[0][1];
// cout<<f0<<" "<<f1<<endl;
if(dp2[1]==1)
{
ans=((n-R2[1])%mod)*f0%mod+n*f1%mod;
}
else ans=R2[1]*f0%mod;
cout<<(ans)%mod;
return 0;
}