大佬
显然假期望
我奇思妙想出了一个式子$f[i]=f[i-1]+sumlimits_{j=1}^{j<=m} C_{k imes j}^{k} imes w[j]$
然后一想不对得容斥
于是我得到$f[i]=f[i-1]+sumlimits_{j=1}^{j<=m} C_{j imes(k-1)}^{k-1} imes w[j]$
但还是不对
现在思考第一个式子为什么不对
我们枚举矩阵选数
1 2 3
1 2 3
1 2 3
这样我们C的话概率会很鬼$frac {4}{12}$$ imes$$frac {3}{11}$$ imes$$frac {2}{10}$
显然应该是$frac 1 3$$ imes $$frac 1 3$$ imes$$frac 1 3$
我算小了
真的是小了吗？
思考第二个式子为什么不对，显然我们如果这样做应该再乘$C_{k}^{1}$但这么乘起来会重复
1111111会被多贡献很多回
还是要容斥
然后考试时我思维就停止了
我们或许可以换种思路考虑
同样是一个区间，我们这样算区间贡献
$sumlimits_{j=1}^{j<=m} j^k-(j-1)^k$
理解一下
$j^k$表示$<=j$随便选，然后再容斥掉$(j-1)^k$（所有都比j小，选不到j）
得到贡献
然后再用f转移即可
#include<bits/stdc++.h> #define ll long long #define A 700000 using namespace std; const ll mod=1e9+7; ll n,m,k,sumday,w[A],ni,ans=0; inline ll meng(ll x,ll k){ ll ans=1; for(;k;k>>=1,x=x*x%mod) if(k&1) ans=ans*x%mod; return ans; } int main(){ scanf("%lld%lld%lld",&n,&m,&k); if(k>n) { puts("0"); return 0; } ni=1; for(ll i=1;i<=m;i++) scanf("%lld",&w[i]); for(ll i=1;i<=m;i++) ((ans=(ans%mod+(meng(i,k)%mod-meng(i-1,k)%mod+mod)*w[i]%mod)%mod))%=mod; ans=ans*(n-k+1)%mod; ni=meng(meng(m,k),mod-2)%mod; cout<<ans%mod*ni%mod<<endl; }
辣鸡
考试历程：
想到$n^2$过不了应该是$n^log$的，或许是$n^{log^2}$
反正$n^2$能过我吃掉键盘
然后我就思考，我tm应该用什么呢，CDQ？树状数组？线段树？权值线段树？还是像上次光那个题一样的傻逼大模拟？
偶对了，一定是像光那个题一样的傻逼题。
但我的光现在还没有过啊。。
这个题暴力分好少啊
然后我还是打了个普通$n^2$然后发现它炸了。
我发现难以调出来还是改成了xy相关
考完后
这个题还真$n^2$能过
完了我没有立flag
后来得知是优化过的$n^2$
打起来像插头dp
首先矩阵内的贡献我们可以用(x2-x1)*(y2-y1)*2算出来
然后矩阵之间分很多种情况
然而每一种都比较简单,比插头简单的多
方格表示过于,,,容易出现各种错误,格点表示
具体还是看代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1100000 struct node{ ll x1,x2,y1,y2; friend bool operator <(const node a,const node b){ return ((a.x1==b.x1)?a.y1<b.y1:a.x1<b.x1); } }nd[A]; ll ans=0,n; int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld%lld%lld",&nd[i].x1,&nd[i].y1,&nd[i].x2,&nd[i].y2); ans+=(nd[i].x2-nd[i].x1)*(nd[i].y2-nd[i].y1)*2; } sort(nd+1,nd+n+1); for(ll i=1;i<n;i++){ for(ll j=i+1;j<=n;j++){ if(nd[j].x1>nd[i].x2+1) break; if(nd[i].y2+1<nd[j].y1||nd[i].y1-1>nd[j].y2) continue; // printf("ix1=%lld iy1=%lld jx1=%lld jy1=%lld ",nd[i].x1,nd[i].y1,nd[j].x1,nd[j].y1); if(nd[j].x1>nd[i].x2){ if(nd[i].y2<nd[j].y1||nd[i].y1>nd[j].y2) ans++; else if(nd[i].y1==nd[j].y1){ if(nd[i].y2==nd[j].y2) ans+=(nd[i].y2-nd[i].y1)*2; else if(nd[i].y2<nd[j].y2) ans+=(nd[i].y2-nd[i].y1)*2+1; else if(nd[i].y2>nd[j].y2) ans+=(nd[j].y2-nd[i].y1)*2+1; } else if(nd[i].y2==nd[j].y2){ if(nd[i].y1==nd[j].y1) ans+=(nd[i].y2-nd[j].y1)*2; else if(nd[i].y1<nd[j].y1) ans+=(nd[i].y2-nd[j].y1)*2+1; else if(nd[i].y1>nd[j].y1) ans+=(nd[i].y2-nd[i].y1)*2+1; } else if(nd[i].y2>nd[j].y2&&nd[i].y1<nd[j].y1) ans+=(nd[j].y2-nd[j].y1)*2+2; else if(nd[i].y2<nd[j].y2&&nd[i].y1<nd[j].y1) ans+=(nd[i].y2-nd[j].y1)*2+2; else if(nd[i].y2>nd[j].y2&&nd[i].y1>nd[j].y1) ans+=(nd[j].y2-nd[i].y1)*2+2; else if(nd[i].y2<nd[j].y2&&nd[i].y1>nd[j].y1) ans+=(nd[i].y2-nd[i].y1)*2+2; // printf("second%lld ",ans); } else{ if(nd[i].x1==nd[j].x1){ if(nd[i].x2==nd[j].x2) ans+=(nd[i].x2-nd[i].x1)*2; else if(nd[i].x2<nd[j].x2) ans+=(nd[i].x2-nd[i].x1)*2+1; else if(nd[i].x2>nd[j].x2) ans+=(nd[j].x2-nd[i].x1)*2+1; } else if(nd[i].x2==nd[j].x2){ if(nd[i].x1==nd[j].x1) ans+=(nd[i].x2-nd[j].x1)*2; else if(nd[i].x1<nd[j].x1) ans+=(nd[i].x2-nd[j].x1)*2+1; else if(nd[i].x1>nd[j].x1) ans+=(nd[i].x2-nd[i].x1)*2+1; } else if(nd[i].x2>nd[j].x2) ans+=(nd[j].x2-nd[j].x1)*2+2; else if(nd[i].x1<nd[j].x1&&nd[i].x2<nd[j].x2) ans+=(nd[i].x2-nd[j].x1)*2+2; // printf("frist%lld ",ans); } // printf("i=%lld j=%lld ans=%lld ",i,j,ans); } } cout<<ans<<endl; }
模板
我一开始确实以为是模板
然后就开始打了,树差,线段树,权值线段树,合并往上仍
不就是和雨天的尾巴差不多的一道题目吗 AC预订
然后越想越不对,觉得难以维护桶
看数据范围不维护桶勉强可以70分
那就先得70分吧
然后我就打炸了,看着最后时间将至赶紧删了打暴力
暴力树上差分还有30分,树上差分打对就行
然后树上差分我觉得也不行,也是相当难维护,set,vector,map,multiset往上仍,但无济于事
最小的点是10 10 10,打个纯暴力还有10分呢
我成功奶死了自己
0分!
tqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltql
说一下这个怎么做
前置知识：
启发式合并
线段树
注意很多细节，我会在启发式合并中具体讲