于是我们今天有迎来了一次愉悦的小测。
早晨签到两发大吉，还有一个宜参加模拟赛？buff--。
然后看到了一个暴力分十分良心，怕不是正解不是给人写的了，buf--。
上午上了三节课，书丢了，下课提前走被老师训了，buf--。
中午13:40考试，迟到是必然的，怕不是要变成NOIP了，buf--。
就这样，我迎来了下午的考试。
T1：有毒的土豆排序：
什么？求逆序对？动态？怕不是树套树？
不行，这样卡n方了。
算了，想想正经方法：
动态维护变化量？写了，对拍，WA了。
肯定是我想的姿势不正确。
用一个树状数组暴力维护。修改的时候用vector记录位置和数值，数值重新排序。
好，70分到手。不管了。
这题目的正解是考虑操作的性质，如果一个数被操作过了那么他后面一定没有比他小的值，然后离线即可。
另外，题面出锅了！必须按照含等于进行计算。我用两次WA证明了这一点。
考场70分代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn=1e3+1e2; 8 9 vector poss;10 int in[maxn],srt[maxn];11 int n,m,cnt,ans;12 13 struct BinaryIndexTree {14 int dat[maxn];15 16 #define lowbit(x) (x&-x)17 18 inline void update(int pos,int x) {19 while( pos <= n )20 dat[pos] += x,21 pos += lowbit(pos);22 }23 inline int query(int pos) {24 int ret = 0;25 while( pos )26 ret += dat[pos],27 pos -= lowbit(pos);28 return ret;29 }30 inline void reset() {31 memset(dat,0,sizeof(dat));32 }33 }bit;34 35 inline void getposs(int fst) {36 poss.clear();37 poss.push_back(fst);38 for(int i=fst+1;i<=n;i++)39 if( in[i] < in[fst] )40 poss.push_back(i);41 }42 inline void replac() {43 static vector nums;44 nums.clear();45 for(unsigned i=0;i
考后AC代码：
1 #include2 #include 3 #include 4 #include 5 #define lli long long int 6 #define lowbit(x) (x&-x) 7 using namespace std; 8 const int maxn=1e5+1e2; 9 const int inf=0x3f3f3f3f; 10 11 int in[maxn],srt[maxn],n,m,cnt; 12 lli iniv[maxn],delt[maxn]; 13 14 struct QNode { 15 int pos,t; 16 friend bool operator < (const QNode &a,const QNode &b) { 17 return a.pos < b.pos; 18 } 19 }ns[maxn]; 20 21 namespace Ini { 22 lli dat[maxn]; 23 inline void update(int pos,int x) { 24 while( pos <= n ) 25 dat[pos] += x, 26 pos += lowbit(pos); 27 } 28 inline lli query(int pos) { 29 lli ret = 0; 30 while( pos ) 31 ret += dat[pos], 32 pos -= lowbit(pos); 33 return ret; 34 } 35 } 36 namespace Bit { 37 int dat[maxn]; 38 inline void update(int pos,int x) { 39 while( pos <= cnt ) 40 dat[pos] = min( dat[pos] , x ), 41 pos += lowbit(pos); 42 } 43 inline int query(int pos) { 44 int ret = *dat; 45 while( pos ) 46 ret = min( ret , dat[pos] ), 47 pos -= lowbit(pos); 48 return ret; 49 } 50 inline void init() { 51 memset(dat,0x3f,sizeof(dat)); 52 } 53 } 54 55 inline void getans() { 56 for(int i=n;i;i--) { 57 Ini::update(in[i],1); 58 iniv[i] = Ini::query(in[i]-1); 59 delt[0] += iniv[i]; 60 } 61 62 int pp = 1; 63 for(int i=1;i<=n;i++) { 64 while( ns[pp].pos == i ) { 65 Bit::update(cnt-in[ns[pp].pos]+1,ns[pp].t); 66 ++pp; 67 } 68 int q = Bit::query(cnt-in[i]+1); 69 if( q != inf ) { 70 delt[q] -= iniv[i]; 71 } 72 } 73 for(int i=1;i<=m;i++) 74 delt[i] += delt[i-1]; 75 } 76 77 inline void init() { 78 Bit::init(); 79 80 sort(srt+1,srt+1+n); 81 cnt = unique(srt+1,srt+1+n) - srt - 1; 82 83 for(int i=1;i<=n;i++) 84 in[i] = lower_bound(srt+1,srt+1+cnt,in[i]) - srt; 85 86 sort(ns+1,ns+1+m); 87 } 88 89 inline int getint() { 90 int ret = 0 , ch; 91 do ch=getchar(); while( !isdigit(ch) ); 92 do ret=ret*10+ch-'0'; while( isdigit(ch=getchar()) ); 93 return ret; 94 } 95 int main() { 96 n = getint() , m = getint(); 97 for(int i=1;i<=n;i++) 98 srt[i] = in[i] = getint(); 99 for(int i=1;i<=m;i++)100 ns[i] = (QNode){getint(),i};101 102 init();103 getans();104 105 for(int i=0;i<=m;i++)106 printf("%lld\n",delt[i]);107 108 return 0;109 }
T2：窝瓜走路：
显然我先写的是这个题。
一看总共9个点，T的范围为long long，矩乘跑不了了。
看一下怎么矩乘，先跑出每对点的方案数，然后再9！枚举哪个点到哪个点。然后方案数连乘更新答案。
100分就这样吧。
代码：
1 #include2 #include 3 #include 4 #include 5 #define lli long long int 6 #define debug cout 7 using namespace std; 8 const int maxn=12; 9 const int mod = 1e9+7;10 11 const int dx[]={-1,1,0,0,0},dy[]={ 0,0,-1,1,0};12 int pre[maxn];13 lli T,ans,now;14 15 struct Matrix {16 lli dat[maxn][maxn];17 Matrix(int tpe = 0) {18 memset(dat,0,sizeof(dat));19 if( tpe )20 for(int i=1;i<=9;i++)21 dat[i][i] = 1;22 }23 friend Matrix operator * (const Matrix &a,const Matrix &b) {24 Matrix ret;25 for(int i=1;i<=9;i++)26 for(int j=1;j<=9;j++)27 for(int k=1;k<=9;k++)28 ret.dat[i][j] = ( ret.dat[i][j] + a.dat[i][k] * b.dat[k][j] % mod ) % mod;29 return ret;30 }31 }base,way;32 33 inline Matrix fastpow(const Matrix &base,lli tme) {34 Matrix now = base , ret = Matrix(1);35 while( tme ) {36 if( tme & 1 )37 ret = ret * now;38 now = now * now;39 tme >>= 1;40 }41 return ret;42 }43 44 inline bool judge(int x,int y) {45 return x > 0 && x <= 3 && y > 0 && y <= 3;46 }47 inline int cov(int x,int y) {48 return ( x - 1 ) * 3 + y;49 }50 inline void init() {51 for(int x=1;x<=3;x++)52 for(int y=1;y<=3;y++)53 for(int k=0;k<5;k++) {54 const int tx = x + dx[k] , ty = y + dy[k];55 if( judge(tx,ty) )56 base.dat[cov(tx,ty)][cov(x,y)] = 1;57 }58 }59 60 inline lli calc() {61 lli ret = 1;62 for(int i=1;i<=9;i++)63 ret = ret * way.dat[i][pre[i]] % mod;64 return ret;65 }66 inline void getans() {67 init();68 way = fastpow(base,T);69 70 for(int i=1;i<=9;i++)71 pre[i] = i;72 73 do {74 ans = ( ans + calc() ) % mod;75 } while( next_permutation(pre+1,pre+10) );76 }77 78 int main() {79 scanf("%lld",&T);80 getans();81 82 printf("%lld\n",ans);83 return 0;84 }
T3：不知道起什么名字好的数学题
很显然的题目。
我一开始用μ反演，然后推出了一个可以用nloglogn筛出的东西，70分到手。
然后考虑怎么优化，提取了一个μ的前缀和，还有某个数的k次方的前缀和。
算法复杂度为n^(3/4)，然而k次方的前缀和手玩玩不出来，弃坑。
正解：用φ反演。
然后杜教筛φ即可。
对于k次方的前缀和，我们能看出他是一个k+1次的多项式，然后高斯消元求解系数即可。
考场70分代码：
1 #include2 #include 3 #include 4 #include 5 #define lli long long int 6 #define debug cout 7 using namespace std; 8 const int maxn=1e6+1e2,lim=1e6; 9 const int mod=1e9+7;10 11 lli sum[maxn];12 int n,k;13 14 inline lli slowpow(lli base) {15 register lli ret = 1;16 for(register int i=k;i;i--)17 ret = ret * base % mod;18 return ret;19 }20 inline void pre() {21 static lli pows[maxn];22 static int prime[maxn],mu[maxn],cnt;23 static unsigned char vis[maxn];24 25 mu[1] = 1 , pows[1] = 1;26 for(lli i=2;i<=n;i++) {27 if( !vis[i] ) {28 prime[++cnt] = i,29 mu[i] = -1 , pows[i] = slowpow(i);30 }31 for(int j=1;j<=cnt&&i*prime[j]<=n;j++) {32 const int tar = i * prime[j];33 vis[tar] = 1 , pows[tar] = pows[i] * pows[prime[j]] % mod;34 if( ! ( i % prime[j] ) ) {35 mu[tar] = 0;36 break;37 }38 mu[tar] = -mu[i];39 }40 }41 for(lli i=1;i<=n;i++)42 if( mu[i] ) {43 for(lli j=1;i*j<=n;j++)44 sum[i*j] += mu[i] * pows[j] % mod ,45 sum[i*j] %= mod;46 }47 for(int i=1;i<=n;i++)48 sum[i] = ( ( sum[i] + sum[i-1] ) % mod + mod ) % mod;49 }50 51 inline lli getans() {52 lli ret = 0;53 for(lli i=1,j;i<=n;i=j+1) {54 j = n / ( n / i );55 ret += ( sum[j] - sum[i-1] ) * ( n / i ) % mod * ( n / i ) % mod;56 ret %= mod;57 }58 return ( ret + mod ) % mod;59 }60 61 int main() {62 scanf("%d%d",&n,&k);63 64 pre();65 66 printf("%lld\n",getans());67 68 return 0;69 }
求解系数代码：
1 #include2 #define lli long long int 3 #define debug cout 4 using namespace std; 5 const int maxn=100; 6 const int mod=1e9+7; 7 8 lli f[maxn][maxn]; 9 int k; 10 11 inline lli rev(int base) { 12 lli now = base , ret = 1 , tme = mod - 2; 13 while(tme) { 14 if( tme & 1 ) 15 ret = ret * now % mod; 16 now = now * now % mod; 17 tme >>= 1; 18 } 19 debug<<"base = "< <<"ret = "< <
考后AC代码：
1 #include2 #include 3 #include 4 #include 5 #define lli long long int 6 #define debug cout 7 using namespace std; 8 const int maxn=5e6+1e2,lim=5e6; 9 const int mod=1e9+7;10 const int muls[6][7] = {11 { 0,0,0,0,0,0,0},12 { 0,500000004,500000004,0,0,0,0},13 { 0,166666668,500000004,333333336,0,0,0},14 { 0,0,250000002,500000004,250000002,0,0},15 { 0,766666672,0,333333336,500000004,400000003,0},16 { 0,0,916666673,0,416666670,500000004,166666668}17 };18 19 lli sum[maxn],mem[maxn];20 unsigned char vis[maxn];21 lli n;22 int k;23 24 inline lli gk(lli x) {25 x %= mod;26 lli ret = 0 , now = 1;27 for(int i=0;i<=k+1;i++) {28 ret += now * muls[k][i] % mod;29 ret %= mod;30 now = now * x % mod;31 }32 return ret;33 }34 35 inline void sieve() {36 static int prime[maxn],cnt;37 38 sum[1] = 1;39 for(lli i=2;i<=lim;i++) {40 if( !sum[i] ) {41 prime[++cnt] = i , 42 sum[i] = i - 1;43 }44 for(int j=1;j<=cnt&&i*prime[j]<=lim;j++) {45 const int tar = i * prime[j];46 if( ! ( i % prime[j] ) ) {47 sum[tar] = sum[i] * prime[j];48 break;49 }50 sum[tar] = sum[i] * ( prime[j] - 1 );51 }52 }53 for(int i=1;i<=lim;i++)54 sum[i] += sum[i-1] ,55 sum[i] %= mod;56 }57 58 inline lli inisum(lli x) {59 x %= mod;60 return ( x * ( x + 1 ) >> 1 ) % mod;61 }62 inline lli getsum(lli x) {63 if( x <= lim )64 return sum[x];65 const int t = n / x;66 if( vis[t] )67 return mem[t];68 vis[t] = 1 , mem[t] = inisum(x);69 for(lli i=2,j;i<=x;i=j+1) {70 j = x / ( x / i );71 mem[t] -= ( j - i + 1 ) * getsum( x / i ) % mod;72 mem[t] %= mod;73 }74 return mem[t] = ( mem[t] + mod ) % mod;75 }76 77 inline lli calcr(lli x) {78 lli ret = ( getsum(x) << 1 ) % mod - 1;79 return ( ret % mod + mod ) % mod;80 }81 inline lli getans() {82 lli ret = 0;83 for(lli i=1,j;i<=n;i=j+1) {84 j = n / ( n / i );85 ret += ( ( gk(j) - gk(i-1) ) % mod + mod ) % mod * calcr( n / i ) % mod;86 ret %= mod;87 }88 return ( ret + mod ) % mod;89 }90 91 int main() {92 scanf("%lld%d",&n,&k);93 sieve();94 95 printf("%lld\n",getans());96 97 return 0;98 }
最后补一张排名：
为何常数如此之大，然后我掉rank了。
