衡阳商城网站制作,2001国产卡一卡二新区,天津网站建设培训班,一个企业seo网站的优化流程文章目录考试复盘rnglgpm考试复盘
第一题#xff0c;乍一看期望#xff0c;又不会做了#xff0c;乍二看#xff0c;暴力好像可以202020跑路#xff0c;屁颠屁颠敲完死活过不了这个简单的样例#xff1b;开始(⊙⊙?)乍三看#xff0c;实数#xff1f;#xff1f;完了…
文章目录考试复盘rnglgpm考试复盘
第一题乍一看期望又不会做了乍二看暴力好像可以202020跑路屁颠屁颠敲完死活过不了这个简单的样例开始(⊙⊙?)乍三看实数完了直接哦豁麻溜拍拍屁股走人
第二题我一看一坨数学公式人直接傻掉_这种直接问公式答案的少不了使劲推式子的过程而且非常了解自己的数学水平肯定不行想法肯定会有就是拆gcdgcdgcd的质因子分开算贡献推了一会儿发现确实不行快速暴力下一个(╥╯^╰╥)
第三题有点感觉自己手玩了几组找了下规律感觉跟逆序对个数和区间长度关系挂钩而且好像都是最多只能减少111因为相比起来做出第三题的概率更大两个小时多都在淦这一道想到了可持久化线段树差分算区间逆序对个数下标和值域是同样区间但是卡在了最后这么找这一段的时间上只会暴力跳ヽ(○㉨)♪
谁曾想xez的算法左扫一遍又扫一遍最后变几个能ACACAC这种做法之高叼
数学题——就是要敢猜先猜后证ball哥教的
rng 考虑对于每个ijijij计算a[i]a[j]a[i]a[j]a[i]a[j]的概率并求和
假设(li,ri)(l1,r1),(lj,rj)(l2,r2)(l_i,r_i)(l_1,r_1),(l_j,r_j)(l_2,r_2)(li,ri)(l1,r1),(lj,rj)(l2,r2)
先从l1l20l_1l_20l1l20入手
若r1≤r2r_1\le r_2r1≤r2则概率为r12r2r122r1r2\frac{r_1}{2r_2}\frac{r_1^2}{2r_1r_2}2r2r12r1r2r12
这个实数的概率很像JJ晚上给我做的物理高必刷必修二里面的一道积分滑动摩擦力做功长度和为nnn的mmm个小物块从光滑面滑入粗糙面利用积分求解的
若r1r2r_1r_2r1r2则概率为1−r22r12r1r2−r222r1r21-\frac{r_2}{2r_1}\frac{2r_1r_2-r_2^2}{2r_1r_2}1−2r1r22r1r22r1r2−r22
r22r1\frac{r_2}{2r_1}2r1r2就是假如jijiji的逆序对概率用111减去则为ijijij时的逆序对概率
用三个树状数组维护1,x,x21,x,x^21,x,x2
接下来考虑(l1,r1),(l2,r2)(l_1,r_1),(l_2,r_2)(l1,r1),(l2,r2)
容斥答案为f(r1,r2)−f(l1,r2)−f(r1,l2)f(l1,l2)2(r1−l1)(r2−l2)\frac{f(r_1,r_2)-f(l_1,r_2)-f(r_1,l_2)f(l_1,l_2)}{2(r_1-l_1)(r_2-l_2)}2(r1−l1)(r2−l2)f(r1,r2)−f(l1,r2)−f(r1,l2)f(l1,l2)
非常常见的二维平面容斥方法
注意不应该直接减概率fff相当于是合法面积
#include cstdio
#include algorithm
using namespace std;
#define maxn 100005
#define int long long
#define mod 998244353
pair int, int p[maxn][2];
int n, cnt;
int l[maxn], r[maxn], x[maxn 1], num[2];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}struct node {int val;int t[maxn 1];int lowbit( int x ) {return x ( -x );}void add( int x, int y ) {val ( val y ) % mod;for( int i x;i cnt;i lowbit( i ) )t[i] ( t[i] y ) % mod;}int query( int x ) {if( x cnt ) return val;int ans 0;for( int i x;i;i - lowbit( i ) )ans ( ans t[i] ) % mod;return ans;}int query( int l, int r ) {return ( query( r ) - query( l - 1 ) ) % mod;}
}A, B, C;#define opt first
#define val secondsigned main() {scanf( %lld, n );for( int i 1;i n;i ) {scanf( %lld %lld, l[i], r[i] );p[i][0] make_pair( -1, l[i] );p[i][1] make_pair( 1, r[i] );x[ cnt] l[i], x[ cnt] r[i];}sort( x 1, x cnt 1 );int ans 0;for( int i 1;i n;i ) {int inv qkpow( r[i] - l[i], mod - 2 );pair int, int now;for( int j 0;j 1;j ) {now p[i][j];num[j] lower_bound( x 1, x cnt 1, now.val ) - x;ans ( ans now.opt * C.query( 1, num[j] ) * inv % mod ) % mod;ans ( ans now.opt * ( B.query( num[j] 1, cnt ) * 2 * now.val % mod- A.query( num[j] 1, cnt ) * now.val % mod * now.val % mod) * inv % mod) % mod; }for( int j 0;j 1;j ) {now p[i][j];A.add( num[j], now.opt * inv % mod );B.add( num[j], now.opt * now.val * inv % mod );C.add( num[j], now.opt * now.val * now.val % mod * inv % mod );}}ans ans * qkpow( 2, mod - 2 ) % mod;printf( %lld\n, ( ans mod ) % mod );return 0;
}lg
∏lcmgcd∏lcm∑d∣xφ(d)\prod lcm^{gcd}\prod lcm^{\sum_{d|x}φ(d)}∏lcmgcd∏lcm∑d∣xφ(d) 指数相加拆出来即为相乘 ∏d∏d∣x∗ilcmφ(d)∏d(∏x∗i≤⌊md⌋(lcm∗d))φ(d)\prod_{d}\prod_{d|x*i}lcm^{φ(d)}\prod_{d}\bigg(\prod_{x*i\le \lfloor\frac{m}{d}\rfloor}(lcm*d)\bigg)^{φ(d)}d∏d∣x∗i∏lcmφ(d)d∏(x∗i≤⌊dm⌋∏(lcm∗d))φ(d) 把ddd拆出来 ∏d(∏x∗i≤⌊md⌋lcm)φ(d)∗dφ(d)∗(⌊md⌋)n\prod_{d}\bigg(\prod_{x*i\le \lfloor\frac{m}{d}\rfloor}lcm\bigg)^{φ(d)}*d^{φ(d)*(\lfloor\frac{m}{d}\rfloor)^n}d∏(x∗i≤⌊dm⌋∏lcm)φ(d)∗dφ(d)∗(⌊dm⌋)n 计算lcmlcmlcm就单独考虑每个质因子的贡献用容斥计算类似于xxx的倍数的个数−-−是x2x^2x2的倍数的个数… Damo的题解
#include cstdio
#define mod 998244353
#define int long long
#define maxn 200005
int n, m, cnt;
int prime[maxn], phi[maxn];
bool vis[maxn];int qkpow( int x, int y, int Mod ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % Mod;x x * x % Mod;y 1;}return ans;
}void sieve() {phi[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, phi[i] i - 1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {phi[i * prime[j]] phi[i] * prime[j];break;}phi[i * prime[j]] phi[i] * ( prime[j] - 1 );}}
}int calc( int m ) {int ans 1;for( int i 1;prime[i] m i cnt;i ) {int res 0;for( int k 1, p prime[i];p m;k , p * prime[i] )//k容斥系数 注意是在算指数上的质因子的贡献 取模是mod-1res ( res k * ( qkpow( m - m / ( p * prime[i] ), n, mod - 1 ) % mod - qkpow( m - m / p, n, mod - 1 ) ) ) % ( mod - 1 );if( res 0 ) res ( mod - 1 );ans ans * qkpow( prime[i], res, mod ) % mod;//每个质因子的贡献相乘 取模是mod}return ans;
}signed main() {sieve();scanf( %lld %lld, n, m );int ans 1, last 0, lcm 0;for( int d 1;d m;d ) {if( ! last || m / d ! last ) {//分块last m / d;lcm calc( m / d );}ans ans * qkpow( lcm, phi[d], mod ) % mod * qkpow( d, phi[d] * qkpow( m / d, n, mod - 1 ) % ( mod - 1 ), mod ) % mod;// 指数上的快速幂取模是phi(mod)mod-1}printf( %lld\n, ans );return 0;
}
pm 考虑一个长度最小为lenlenlen的段一定操作了len−1len-1len−1次否则该段一定可以分成两个更小的段各自独立操作
不然就直接lenlenlen次一一单独变化即可
而且len−1len-1len−1次操作后下标和值就应该一一对应了
问题转换成在原序列中找出若干不相交的段每个段的长度等于这个段中的逆序对个数111并且每个段占用的下标和包含的元素集合相同每个这样的段都能省一次操作
考虑对于每个段右端点如果有 找到最短的占用下标和包含元素集合相同的段 只有这样的段是候选段
如果选取了更长的段显然可以用这个段将它分开 并且分开的两段中也恰有一段满足逆序对个数比长度少一
接下来需要对于每个段的右端点rrr找到最短的段[l,r][l,r][l,r]满足{al,al1...ar}[l,r]\{a_l,a_{l1}...a_{r}\}[l,r]{al,al1...ar}[l,r]
max{al,...,ar}rmax\{a_l,...,a_r\}rmax{al,...,ar}r可以用ststst表预处理
sumilrai−i0sum_{il}^ra_i-i0sumilrai−i0扫一遍就可以做了一段区间和为000说明前lll和前rrr和一样
nxd[l,r]r−lnxd[l,r]r-lnxd[l,r]r−l转化为差分
#include map
#include cmath
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 200005
map int, int last;
int n, cnt;
int a[maxn], id[maxn], nxd[maxn], L[maxn], ans[maxn];
int tree[maxn], f[maxn], g[maxn], pre[maxn];
int rt[maxn], t[maxn * 30], lson[maxn * 30], rson[maxn * 30];
int st[maxn][20];int lowbit( int x ) {return x ( -x );
}void add( int x ) {x n - x 1;for( int i x;i n;i lowbit( i ) )tree[i] ;
}int query( int x ) {x n - x 1;int tot 0;for( int i x;i;i - lowbit( i ) )tot tree[i];return tot;
}void insert( int pre, int now, int l, int r, int pos ) {if( ! now ) now cnt;t[now] t[pre] 1;if( l r ) return;int mid ( l r ) 1;if( pos mid ) rson[now] rson[pre], insert( lson[pre], lson[now], l, mid, pos );else lson[now] lson[pre], insert( rson[pre], rson[now], mid 1, r, pos );
}int query( int now, int l, int r, int L, int R ) {if( L R ) return 0;if( L l r R ) return t[now];int mid ( l r ) 1;if( R mid ) return query( lson[now], l, mid, L, R );else if( mid L ) return query( rson[now], mid 1, r, L, R );else return query( lson[now], l, mid, L, R ) query( rson[now], mid 1, r, L, R );
}void init() {for( int i 1;i n;i ) st[i][0] a[i];for( int j 1;j 20;j )for( int i 1;i n;i )if( i ( 1 j - 1 ) n ) break;else st[i][j] max( st[i][j - 1], st[i ( 1 j - 1 )][j - 1] );
}int ask( int l, int r ) {int i log( r - l 1 ) / log( 2 );return max( st[l][i], st[r - ( 1 i ) 1][i] );
}signed main() {scanf( %lld, n );int sum 0;last[0] 1;for( int i 1;i n;i ) {scanf( %lld, a[i] );insert( rt[i - 1], rt[i], 1, n, a[i] );nxd[i] nxd[i - 1] query( a[i] 1 );add( a[i] );sum a[i] - i;L[i] last[sum];//上一次sum的位置与现在sum的位置中间的和即为0last[sum] i 1;id[a[i]] i;}init();for( int i 1;i n;i ) {if( L[i] ) {//如果成段int l L[i], r i;int tot nxd[r] - nxd[l - 1] - query( rt[l - 1], 1, n, r 1, n ) * ( r - l 1 );//[1,l-1]对于[l,r]区间的逆序对数量就是[1,l-1]中大于r的个数*(r-l1),[l,r]值出现的位置一定是在区间[l,r]if( tot r - l ask( l, r ) r ) {f[i] f[pre[l - 1]] 1;//段数1g[i] pre[l - 1];//上一个段的结束位置}}pre[i] pre[i - 1];//递推传递上一个段的结束位置if( f[pre[i - 1]] f[i] ) pre[i] i;//新段的右端点}cnt 0;int r pre[n];while( r ) {int l L[r];for( int i r;i l;i -- )for( int j id[i];j i;j ) {swap( id[a[j]], id[a[j 1]] );swap( a[j], a[j 1] );ans[ cnt] j;}r g[r];}printf( %d\n, cnt );for( int i 1;i cnt;i )printf( %d , ans[i] );return 0;
}
