教我C题的杭电大佬、叉姐的题解（看了还是啥也不会）
求上述式子的值，输出对分数取模的值，ai<=1e9,n<=1e3
赛中的时候用裂项拆项把两项相乘拆成两项相减，转移为长度-1的子问题，n方dp搞过去了
#include<bits/stdc++.h> const int mod=1e9+7; typedef long long ll; using namespace std; const int N=1e3+10; ll n,a[N],b[N],dp[N][N]; ll modpow(ll x,ll n,ll mod) { ll ans=1; for(;n;n/=2,x=x*x%mod) if(n&1)ans=ans*x%mod; return ans; } ll upd(ll a) { a%=mod; if(a<0)a+=mod; return a; } ll solve(ll l,ll r) { if(~dp[l][r])return dp[l][r]; if(l==r)return dp[l][r]=modpow(upd(2*a[l]),mod-2,mod); return dp[l][r]=upd(solve(l,r-1)-solve(l+1,r))*modpow(upd(b[r]-b[l]),mod-2,mod)%mod; } int main() { while(~scanf("%lld",&n)) { for(int i=1;i<=n;++i) memset(dp[i],-1,sizeof dp[i]); for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); b[i]=a[i]*a[i]; } printf("%lld\n",solve(1,n)); } return 0; }思路来源：https://blog.csdn.net/qq_41730082/article/details/96443875#commentsedit
待定系数设原式=C1/(a1^2 + x^2) + C2/(a2^2 + x^2) + …… + Cn/(an^2 + x^2) ，对于任意x都成立
要求C1，把整个式子两端同乘以(a1^2 + x^2)，
这样原式分母里没有(a1^2 + x^2)，且右边C2到Cn每一项都有分子(a1^2 + x^2)，
此时令x=-a1，消去右边这些分子有(a1^2 + x^2)的项，解得C1，其余Ci同理
#include<bits/stdc++.h> const int mod=1e9+7; typedef long long ll; using namespace std; const int N=1e3+10; ll n,a[N],b[N],ans; ll modpow(ll x,ll n,ll mod) { ll res=1; for(;n;n/=2,x=x*x%mod) if(n&1)res=res*x%mod; return res; } int main() { while(~scanf("%lld",&n)) { ans=0; for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); b[i]=a[i]*a[i]; } for(int i=1;i<=n;++i) { ll mul=1; for(int j=1;j<=n;++j) { if(j==i)continue; mul=mul*((b[j]-b[i])%mod+mod)%mod; } ans+=modpow(mul%mod*2*a[i]%mod,mod-2,mod); if(ans>=mod)ans%=mod; } printf("%lld\n",ans); } return 0; }在n(n<=1e4)维空间内有一点A(a1/m,a2/m,...,an/m)(1<=m<=1e3,-m<=ai<=m)，
求一点B，B的每维非负，且和为1，使得AB的欧几里得距离的平方最小，其为对应维度的距离的平方之和
可以证明最终结果是一个有理数，以分数格式输出
考虑要求和的式子，令
即分配完非负的m*p[i]使总和为m，且令和最小，考虑的导数为，那么越近零越好
由于分配的值非负，所以只能把导数往上加，那么应该先加负的，再加正的
对于负数，先处理导数绝对值最大的(也就是值最小的)，这样降的△量最大，
对于正数，先处理导数最小的，这样增的△量最小
所以先将从小到大排序，然后将前i个的导数都分配为第i个的值，
当到第k个无法分配时退出，并将m剩余量摊回给前k个
注意到耗费相同的分配值，分配给导数最小的那些值，对答案起的贡献最大，
所以，就一层一层地往上提最小的导数，直到不能提为止
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e4+5; ll n,m,a[N],x[N],now; ll i,son,fa,g; //sigma((m*p[i]-a[i])*(m*p[i]-a[i]))/(m*m) //x[i]=m*p[i]-a[i] 初始令x[i]=-a[i],分配m*p[i]使总和为m //若最后余now 均分给前k个 int main() { while(~scanf("%lld%lld",&n,&m)) { for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); x[i]=-a[i]; } sort(x+1,x+n+1); now=m; for(i=1;i<n;++i) { if((x[i+1]-x[i])*i>now)break;//把前面所有值都降到x[i+1] now-=(x[i+1]-x[i])*i; } son=(now+x[i]*i)*(now+x[i]*i);//(now/i+x[i]*i)*(now/i+x[i]*i)*i 分子分母同乘i fa=i*m*m; for(int j=i+1;j<=n;++j) son+=i*x[j]*x[j]; g=__gcd(son,fa); son/=g;fa/=g; if(fa==1)printf("%lld\n",son); else printf("%lld/%lld\n",son,fa); } return 0; }现有长度为2*(n+m)(n,m<=1e3)的只由A和B构成的串，求满足下列条件的串的个数
条件：串可以被拆成n+m个长度为2的互不重叠的子序列，使得其中恰有n个为AB，m个为BA
假设dp[i][j]表示为当前有i个A字母，j个B字母且匹配了min(i,j)个A、B对，我们可以适当安排使得其为AB或BA
但无论怎么安排，多出来的那些字母只能当后续字母的前缀，
即若i>j，i-j个A只能去配AB；同理，若j>i，j-i个B只能去配AB，
所以存在一个对后续状态的影响问题，当i-j>n时，后续还要配>n个AB，这显然不满足题意要求，j-i>m同理，
其余都可行，认为当前状态合法，才能转移到下一个合法状态
实际实现时，可以考虑只记录A、B的差值，用偏移量来维护，每次枚举这一位填A还是填B
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=2e3+5; const int off=1050; int n,m,dp[2*N][2*N];//dp[i][j] 表示到第i个字母 A比B多j个 int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=2*(n+m);++i) memset(dp[i],0,sizeof dp[i]); dp[0][off]=1; for(int i=1;i<=2*(n+m);++i) { for(int j=-m;j<=n;++j) { if(j-1>=-m)(dp[i][j+off]+=dp[i-1][j-1+off])%=mod; if(j+1<=n)(dp[i][j+off]+=dp[i-1][j+1+off])%=mod; } } printf("%d\n",dp[2*(m+n)][off]); } return 0; }给三个点坐标ABC(xi,yi)(|xi|,|yi|<=1e8)，不保证一定构成三角形
在构成三角形的条件下，在形内随机掷点P，连接PA PB PC，将每次的贡献记为三个三角形最大的那个的面积
求36*面积的期望值E
据叉姐讲是梅涅劳斯定理，会这题的大佬daidaiwo呀……
后记：https://www.cnblogs.com/WAautomaton/p/11211864.html 变积分为期望的做法
答案是22倍三角形面积，即11倍向量叉积
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll>P; #define fi first #define se second P a[3]; int main() { while(~scanf("%lld%lld%lld%lld%lld%lld",&a[0].fi,&a[0].se,&a[1].fi,&a[1].se,&a[2].fi,&a[2].se)) { for(int i=1;i<3;++i) { a[i].fi-=a[0].fi; a[i].se-=a[0].se; } ll res=(a[1].fi*a[2].se-a[1].se*a[2].fi); if(res<0)res=-res; printf("%lld\n",res*11); } return 0; }给你n(n<=1e5)个整数，第i个数为ai(ai<=1e18)，
若子集S的异或和的0，则将S的大小|S|加到答案中去，求答案
思路来源：https://blog.nowcoder.net/n/01d1e47b322845f2b931adef91ce31bb
考虑枚举每个i的贡献，即对于ai，它在多少个异或和为0的集合中，最后求和
先求出原序列的异或线性基b，其秩为|r|，考虑n-|r|个非基元素
①枚举的值x是非基元素，从n-|r|个非基元素中取出一个，n-|r|种取法
对于每种取法，剩n-|r|-1个非基元素，每个值都可以可选可不选二选一，种可能凑出来的集合T，
而线性基一定能异或出一个一样的集合V，使得T∪V异或和为0
②枚举的值x是基b内元素，考虑对n-|r|个非基元素再做一个线性基other，
other需要将（基b去掉x的基）合并进来，记为基tmptmp一定能异或出除x外的所有值，
如果tmp能异或出x，则这个值对答案的贡献为，证明同①
否则，tmp无论怎么取，都不能使必选出x的集合异或和为0，没贡献
考虑到插入基b的过程会不断异或使得a[i]发生变化，所以开一个vector存一下基b中对应的原值
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int lg=70; const int N=1e5+10; vector<ll>c;//存b基内的原值 int n,sz,tot;//tot 当前在基内的元素个数 ll ans; ll a[N],b[lg],other[lg],tmp[lg];//三个基 bool vis[N]; int modpow(int x,int n,int mod) { int ans=1; for(;n;n/=2,x=1ll*x*x%mod) if(n&1)ans=1ll*ans*x%mod; return ans; } bool ins(ll x,ll base[]) { for(int i=63;i>=0;--i) { if(x&(1ll<<i)) { if(base[i])x^=base[i]; else { base[i]=x; return true; } } } return false; } int main() { while(~scanf("%d",&n)) { for(int i=0;i<=63;++i) b[i]=other[i]=0; c.clear(); tot=0; for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); vis[i]=0; if(ins(a[i],b)) { tot++; vis[i]=1; c.push_back(a[i]); } } if(tot==n) { puts("0"); continue; } ans=1ll*modpow(2,n-tot-1,mod)*(n-tot)%mod; for(int i=1;i<=n;++i) { if(vis[i])continue; ins(a[i],other); } sz=c.size(); for(int i=0;i<sz;++i)//枚举基内元素x { tot=0; for(int j=0;j<=63;++j) tmp[j]=0; for(int j=0;j<=63;++j)//插other if(other[j]&&ins(other[j],tmp))tot++; for(int k=0;k<sz;++k)//插b原值即c if(k!=i&&ins(c[k],tmp))tot++; if(!ins(c[i],tmp))ans=(ans+modpow(2,n-tot-1,mod))%mod;//x插不进tmp基内 所以说明可以异或出x } printf("%lld\n",ans); } return 0; }留坑待补
给两个分数x/a和y/b(0<=x,y<=1e18,1<=a,b<=1e9)，比较大小
分数比较大小，可能会爆long long，赛中是java大数过的
先比较整数部分，再比较余数部分，余数分子肯定小于max(a,b)，max(a,b)*max(a,b)不爆long long
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll x,a,y,b; ll u[2],v[2]; int main() { while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b)) { u[0]=x/a;u[1]=y/b; if(u[0]<u[1])puts("<"); else if(u[0]>u[1])puts(">"); else { v[0]=x%a;v[1]=y%b; if(v[0]*b<v[1]*a)puts("<"); else if(v[0]*b>v[1]*a)puts(">"); else puts("="); } } return 0; }
