Codeforces Round #415 (Div. 1) (CDE)
1. CF 809C Find a car
大意: 给定一个$1e9\times 1e9$的矩阵$a$, $a_{i,j}$为它正上方和正左方未出现过的最小数, 每个询问求一个矩形内的和.
可以发现$a_{i,j}=(i-1)\oplus (j-1)+1$, 暴力数位$dp$即可
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head //求 0<=i<=x, 0<=j<=y, 0<=i^j<=k的所有i^j的和
int f[][][][], g[][][][];
void add(int &a, ll b) {a=(a+b)%P;}
//f为个数, g为和
int calc(int x, int y, int k) {
if (x<||y<) return ;
memset(f,,sizeof f);
memset(g,,sizeof g);
f[][][][] = ;
PER(i,,)REP(a1,,)REP(a2,,)REP(a3,,) {
int &r = f[i+][a1][a2][a3];
if (!r) continue;
int l1=a1&&!(x>>i&),l2=a2&&!(y>>i&),l3=a3&&!(k>>i&);
REP(b1,,)REP(b2,,) {
if (l1&&b1) continue;
if (l2&&b2) continue;
if (l3&&(b1^b2)) continue;
int c1=a1&&b1>=(x>>i&),c2=a2&&b2>=(y>>i&),c3=a3&&(b1^b2)>=(k>>i&);
add(f[i][c1][c2][c3],r);
add(g[i][c1][c2][c3],g[i+][a1][a2][a3]*2ll+(b1^b2)*r);
}
}
int ans = ;
REP(a1,,)REP(a2,,)REP(a3,,) add(ans,g[][a1][a2][a3]+f[][a1][a2][a3]);
return ans;
} int main() {
int t;
scanf("%d", &t);
while (t--) {
int x1,y1,x2,y2,k;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
--x1,--y1,--x2,--y2,--x1,--y1,--k;
int ans = (calc(x2,y2,k)-calc(x1,y2,k)-calc(x2,y1,k)+calc(x1,y1,k))%P;
if (ans<) ans += P;
printf("%d\n", ans);
}
}
2. CF 809D
3. CF 809E Surprise me!
大意: 给定树, 点$i$权值$a_i$, $a$为$n$排列, $dis(x,y)$为$x,y$路径上的边数, 求$\frac{1}{n(n-1)}\sum\limits_{x\not = y} \varphi(a_xa_y)dis(x,y)$
设$b=a^{-1}$, 转化为求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n \varphi(ij)dis(b_i,b_j)$
根据$\varphi(ij)=\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}$
反演一下可以化为$\sum\limits_{T=1}^n\Bigg(\sum\limits_{d\mid T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})\Bigg)\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\varphi(jT)dis(b_{iT},b_{jT})$
考虑枚举$T$, 左边的$\sum\limits_{d\mid T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})$可以线性筛预处理出来.
右边的就是$\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\varphi(jT)({dep}_{b_{iT}}+{dep}_{b_{jT}}-2{dep}_{lca(b_{iT},b_{jT})}) $
预处理一下$\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)$, 那么$\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\varphi(jT)({dep}_{b_{iT}}+{dep}_{b_{jT}})$就很容易求出.
现在只需要考虑求$\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\varphi(jT){dep}_{lca(b_{iT},b_{jT})}$
有效的点数是$O(\frac{n}{T})$的, 提出来建一棵虚树然后$DP$即可
那么总的复杂度就为$O(nlogn)$
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head const int N = 1e6+;
int n,dep[N],fa[N],son[N],top[N];
int phi[N],a[N],b[N],sz[N];
int p[N], cnt, vis[N];
int h[N],L[N],R[N],f[N],s[N],sum[N];
vector<int> g[N],gg[N];
void init() {
phi[] = h[] = ;
for (int i=; i<N; ++i) {
if (!vis[i]) p[++cnt]=i,phi[i]=i-,h[i]=inv(i-);
for (int j=,t; j<=cnt&&i*p[j]<N; ++j) {
vis[t=i*p[j]]=;
if (i%p[j]==) {phi[t]=phi[i]*p[j],h[t]=;break;}
phi[t]=phi[i]*phi[p[j]];
h[t]=(ll)h[i]*h[p[j]]%P;
}
}
}
void dfs(int x, int f, int d) {
L[x]=++*L,dep[x]=d,sz[x]=,fa[x]=f;
for (int y:g[x]) if (y!=f) {
dfs(y,x,d+),sz[x]+=sz[y];
if (sz[y]>sz[son[x]]) son[x]=y;
}
R[x]=*L;
}
void dfs(int x, int tf) {
top[x]=tf;
if (son[x]) dfs(son[x],tf);
for (int y:g[x]) if (!top[y]) dfs(y,y);
}
int lca(int x, int y) {
while (top[x]!=top[y]) {
if (dep[top[x]]<dep[top[y]]) swap(x,y);
x = fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
bool cmp(int x, int y) {
return L[x]<L[y];
} int DP(int x) {
int ans = (ll)f[x]*f[x]%P*dep[x]%P;
sum[x] = f[x];
for (int y:gg[x]) {
ans = (ans+DP(y))%P;
ans = (ans+2ll*sum[y]*sum[x]%P*dep[x])%P;
sum[x] = (sum[x]+sum[y])%P;
}
return ans;
} int solve(vector<int> &a) {
sort(a.begin(),a.end(),cmp);
int sz = a.size();
REP(i,,sz-) a.pb(lca(a[i],a[i-]));
a.pb();
sort(a.begin(),a.end(),cmp);
a.erase(unique(a.begin(),a.end()),a.end());
s[cnt=]=a[],sz=a.size();
REP(i,,sz-) {
while (cnt>=) {
if (L[s[cnt]]<=L[a[i]]&L[a[i]]<=R[s[cnt]]) {
gg[s[cnt]].pb(a[i]);
break;
}
--cnt;
}
s[++cnt]=a[i];
}
int t = DP();
for (auto &x:a) gg[x].clear(),f[x]=sum[x]=;
return t;
} int main() {
init();
scanf("%d",&n);
REP(i,,n) scanf("%d",a+i),b[a[i]]=i;
REP(i,,n) {
int u, v;
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}
dfs(,,),dfs(,);
int ans = ;
REP(T,,n) {
int ret = , sum = ;
REP(i,,n/T) sum = (sum+phi[i*T])%P;
vector<int> v;
REP(i,,n/T) {
ret=(ret+2ll*sum*phi[i*T]%P*dep[b[i*T]])%P;
v.pb(i*T);
}
for (auto &t:v) f[b[t]] = phi[t], t = b[t];
ret = (ret-2ll*solve(v))%P;
ans = (ans+(ll)h[T]*ret)%P;
}
ans = (ll)ans*inv(n)%P*inv(n-)%P;
if (ans<) ans += P;
printf("%d\n",ans);
}
最新文章
- ORACLE分区表梳理系列(二)- 分区表日常维护及注意事项(红字需要留意)
- Ubuntu 14.04 无线网卡驱动安装
- java 27 - 2 反射之 反射的概述以及获取Class文件对象的方式
- linux后台开发排错常用工具
- ARM处理器启动流程
- SecureCRT自动记录日志【记录键入的所有命令和打印的结果信息】
- 数字信号处理Day2-小波基与规范正交化
- CF-Approximating a Constant Range
- json 帮助工具
- python之gui-tkinter可视化编辑界面 自动生成代码
- 「NOI2013」树的计数 解题报告
- Manjaro 安装svn客户端,以及checkout使用命令
- centos系统下安装python3以及pip3
- php之二叉树
- vue 小知识
- 17.docker及scrapy-splash安装-1
- CVE-2013-2551
- RabbitMQ Headers Exchange示例
- High accuracy voltage regulator
- POJ1639顶点度限制最小生成树