首页 > 代码库 > 51nod 最近刷题 简要题解
51nod 最近刷题 简要题解
51nod 1564
由于数据是随机的，可以证明，对于每一个数，向左或右找比它小的数，长度是logn级别的
考虑枚举最大值
注意，对于每一个最大值，如果直接用2个循环枚举左右端点的话，理论是lognlogn级别的，但是还是很容易被卡的，换成贪心，用2个指针指着左右端点，每一次移动我们往数大的那个方向移动
代码：
//File Name: nod1564.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月10日 星期一 19时59分32秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#define LL long longusing namespace std;const int MAXN = 100000 + 5;const LL INF = (1<<18);LL a[MAXN],ans[MAXN];int l[MAXN],r[MAXN];void solve(int n){ l[1] = 1; for(int i=2;i<=n;i++){ l[i] = i; while(l[i] > 1 && a[l[i]-1] <= a[i]) l[i] = l[l[i]-1]; } r[n] = n; for(int i=n-1;i>0;i--){ r[i] = i; while(r[i] < n && a[r[i]+1] < a[i]) r[i] = r[r[i]+1]; } memset(ans,0,sizeof ans); for(int i=1;i<=n;i++){ LL mi1 = a[i];/* for(int j=i;j>=l[i];j--){ mi1 = min(mi1,a[j]); LL mi2 = mi1; for(int k=i;k<=r[i];k++){ mi2 = min(mi2,a[k]); ans[k-j+1] = max(ans[k-j+1],a[i] * mi2); } }*/ int j = i,k = i; while(true){ ans[k-j+1] = max(ans[k-j+1],mi1 * a[i]); if(j == l[i] && k == r[i]) break; else if(j == l[i] && k < r[i]) k+=1,mi1 = min(mi1,a[k]); else if(j > l[i] && k == r[i]) j-=1,mi1 = min(mi1,a[j]); else{ if(a[j-1] >= a[k+1]) j-=1,mi1 = min(mi1,a[j]); else k+=1,mi1 = min(mi1,a[k]); } } } for(int i=n-1;i>=1;i--) ans[i] = max(ans[i],ans[i+1]);}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",a + i); solve(n); for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0;}
51nod 1375
给出n个数，问从中找出刚好k个数或者任意个数，使得这些数的gcd = 1的方案数
枚举gcd，mobius反演下就可以了
代码：
//File Name: nod1375.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月10日 星期一 13时28分47秒 #include <stdio.h>#include <algorithm>#include <iostream>#include <string.h>#define LL long longusing namespace std;const int MOD = 998244353;const int MAXN = 1000000 + 1;const int N = 100000 + 1;int s[MAXN],K;int mu[MAXN],prime[MAXN];bool check[MAXN];LL p2[N],jie[N];LL qp(LL x,LL y){ LL res = 1; for(;y>0;y>>=1){ if(y & 1) res = res * x % MOD; x = x * x % MOD; } return res;}LL C(LL x,LL y){ if(y < 0 || y > x) return 0; if(y == 0 || y == x) return 1; return jie[x] * qp(jie[y] * jie[x-y] % MOD,MOD - 2) % MOD;}void mobius(){ memset(check,false,sizeof check); mu[1] = 1; int tot = 0; for(int i=2;i<MAXN;i++){ if(!check[i]){ prime[tot++] = i; mu[i] = -1; } for(int j=0;j<tot;j++){ if(i * prime[j] >= MAXN) break; check[i * prime[j]] = true; if(i % prime[j] == 0){ mu[i * prime[j]] = 0; break; } else{ mu[i * prime[j]] = -mu[i]; } } }}void init(){ p2[0] = jie[0] = 1; for(int i=1;i<N;i++){ p2[i] = p2[i-1] * 2 % MOD; jie[i] = jie[i-1] * i % MOD; } mobius();}LL cal(int sum){ if(K == -1) return p2[sum] - 1; return C(sum,K);}LL solve(int n,int ma){ LL ans = 0; for(int k=1;k<=ma;k++){ int sum = 0; for(int i=k;i<=ma;i+=k) sum += s[i]; ans = (ans + mu[k] * cal(sum) + MOD) % MOD; } return ans;}int main(){ init(); int n,ma = 0; scanf("%d %d",&n,&K); for(int i=0,u;i<n;i++){ scanf("%d",&u); ma = max(ma,u); s[u]++; } printf("%lld\n",solve(n,ma)); return 0;}
51nod 1269
简单容斥，求组合数的时候C(n，m) % p,虽然n是10^16级别的，但是p是素数，m才20左右，直接暴力求就可以了
//File Name: nod1269.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月10日 星期一 13时11分23秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#define LL long longusing namespace std;const int MOD = (int)1e9 + 7;int inv[20];LL a[20];LL qp(LL x,LL y){ LL res = 1; for(;y>0;y>>=1){ if(y & 1) res = res * x % MOD; x = x * x % MOD; } return res;}LL C(LL x,LL y){ if(x < y || y < 0) return 0; if(y == x || y == 0) return 1; LL ans = 1; for(int i=0;i<y;i++){ ans = (x - i) % MOD * inv[y - i] % MOD * ans % MOD; }// printf("x = %lld y = %lld ans = %lld\n",x,y,ans); return ans;}LL solve(int n,LL s){ for(int i=1;i<n;i++) inv[i] = qp(i,MOD - 2); LL ans = 0; for(int i=0;i<(1<<n);i++){ LL now = 0; int num = 0; for(int j=0;j<n;j++){ if(i & (1 << j)){ num++; now += a[j] + 1; } } LL tmp = C(s - now + n -1,n - 1); if(num & 1) ans = (ans - tmp + MOD) % MOD; else ans = (ans + tmp) % MOD; } return ans;}int main(){ LL s; int n; scanf("%d %lld",&n,&s); for(int i=0;i<n;i++) scanf("%lld",a + i); cout << solve(n,s) << endl; return 0;}
51nod 1407
i表示集合的状态
f(i)表示i & x= i的x的个数，即i是x的子集
可以分治求f
然后容斥下就可以
//File Name: nod1407.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月09日 星期日 22时04分55秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#define LL long longusing namespace std;const int MAXN = 1 << 20;const int MOD = (int)1e9 + 7;int f[MAXN];LL p2[MAXN];void init(){ p2[0] = 1; for(int i=1;i<MAXN;i++) p2[i] = p2[i-1] * 2 % MOD;}void cal(int pre,int i){ if(i < 0) return ; cal(pre,i-1); cal(pre+(1<<i),i-1); for(int j=0;j<(1<<i);j++) (f[pre+j] += f[pre+(1<<i)+j] )%=MOD;}LL solve(int n){ cal(0,19);// for(int i=0;i<=10;i++)// cout << f[i] << endl; LL ans = 0; for(int i=0,s;i<(1<<20);i++){ s = 0; for(int j=0;j<20;j++) if(i & (1<<j)) s++; LL tmp = (p2[f[i]] - 1 + MOD) % MOD; if(s & 1) ans = (ans - tmp + MOD) % MOD; else ans = (ans + tmp) % MOD; } return ans;}int main(){ init(); int n; scanf("%d",&n); for(int i=0,a;i<n;i++){ scanf("%d",&a); f[a]++; } cout << solve(n) << endl; return 0;}
51nod 1406
与上一道题一样
//File Name: nod1406.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月09日 星期日 11时53分29秒 #include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;int f[1<<20];void solve(int pre,int i){ if(i < 0) return ; solve(pre,i-1); solve(pre+(1<<i),i-1); for(int j=0;j<(1<<i);j++) f[pre+j] += f[pre+(1<<i)+j];}int main(){ int n; scanf("%d",&n); for(int i=0,u;i<n;i++){ scanf("%d",&u); f[u]++; } solve(0,19); for(int i=0;i<=1000000;i++) printf("%d\n",f[i]); return 0;}
51nod 1362
枚举向右下方走的次数，可以得到公式
对于公式，有一问题，就是要求的是C(n,m)%p,这个时候p也可能是合数，n是10^9级别，但是m是1000级别的
注意到需要消除的数都是与p的gcd大于1的，所以只需要考虑p的质因子，将与p互质的部分直接求逆元计算，不互质的部分维护成质因子的幂次，从分子中减去即可。
O(nlogp)级别
//File Name: nod1362.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月09日 星期日 19时14分21秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#include <vector>#define LL long longusing namespace std;vector<int> dive;int s[50];LL mod;LL qp(LL x,LL y){ LL res = 1; for(;y>0;y>>=1){ if(y & 1) res = res * x % mod; x = x * x % mod; } return res;}LL ext_gcd(LL a,LL b,LL &x,LL &y){ if(a == 0 && b == 0) return -1; if(b == 0){x = 1;y = 0;return a;} LL d = ext_gcd(b,a%b,y,x); y -= a / b * x; return d;}LL inv(LL a,LL n){ LL x,y; LL d = ext_gcd(a,n,x,y); if(d == 1) return (x % n + n) % n; return -2;}void cal_dive(LL p){ dive.clear(); for(int i=2;i*i<=p;i++){ if(p % i == 0){ dive.push_back(i); while(p % i == 0) p /= i; } } if(p > 1) dive.push_back(p); sort(dive.begin(),dive.end());}LL fact(LL x,int f){ for(int i=0;i<dive.size();i++){ while(x % dive[i] == 0){ s[i]+=f; x /= dive[i]; } } if(f == -1) return inv(x,mod); return x;}LL cal(LL l,LL r,LL a,LL b,LL c){ memset(s,0,sizeof s); LL ans = fact(a,-1); for(int i=2;i<=b;i++) ans = ans * fact(i,-1) % mod; for(int i=2;i<=c;i++) ans = ans * fact(i,-1) % mod; for(LL i=l;i<=r;i++) ans = ans * fact(i,1) % mod; for(int i=0;i<dive.size();i++){ ans = ans * qp(dive[i],s[i]) % mod; } return ans;}LL solve(LL n,LL m){ LL ans = 0; LL ma = min(n,m); cal_dive(mod); for(int c=0;c<=ma;c++){ ans = (ans + cal(m-c+1,m-c+1+n,n+1,c,n-c)) % mod; } return ans;}int main(){ LL n,m; cin >> n >> m >> mod; cout << solve(n,m) << endl; return 0;}
51nod 1197
由于每次跳跃都是*2的，字符串实际上可以划分成若干条链的组合，每一条链都是logn长度的
再加个矩阵乘法
//File Name: nod1197.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月08日 星期六 20时18分58秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#define LL long longusing namespace std;const int MAXN = 1000000 + 2;const int MOD = (int)1e9 + 7;const int N = 22;int f[MAXN][N],len[N],g[N];struct matrix_t{ LL x[N][N]; matrix_t(int v){ memset(x,0,sizeof(x)); for(int i=1;i<=N;i++) x[i][i] = v; } matrix_t operator*(const matrix_t &r){ matrix_t p(0); for(int k=1;k<=N;k++){ for(int i=1;i<=N;i++){ if(x[i][k] == 0) continue; for(int j=1;j<=N;j++){ p.x[i][j] += x[i][k] * r.x[k][j] % MOD; p.x[i][j] %= MOD; } } } return p; } matrix_t power(LL p){ matrix_t r(1),a = *this; for(;p;p>>=1){ if(p & 1) r = r * a; a = a * a; } return r; }};LL solve(int n,LL m){ f[0][0] = 1; for(int i=1;i<=n;i++){ f[i][0] = 1; for(int j=1;j<=20;j++) f[i][j] = (0LL + f[i-1][j] + f[i/2][j-1]) % MOD; } for(int i=1;i<=20;i++) len[i] = (0LL + f[n][i] - f[n/2][i] + MOD) % MOD; matrix_t mat(0); for(int i=1;i<=20;i++) mat.x[1][i] = len[i]; for(int i=2;i<=21;i++) mat.x[i][i-1] = 1; g[0] = 1; for(int i=1;i<N;i++) for(int j=1;j<=20 && j <= i;j++) g[i] = (0LL + g[i] + 1LL * g[i-j] * len[j] % MOD) % MOD; if(m < N) return g[m]; mat = mat.power(m - 21); LL ans = 0; for(int i=1;i<N;i++) ans = (0LL + ans + mat.x[1][i] * g[N - i] % MOD) % MOD; return ans;}int main(){ int n; LL m; cin >> n >> m; cout << solve(n,m) <<endl; return 0;}
51nod 1251
枚举出现最大频率的那个频率，对于剩下的容斥就可以，发现对于枚举i，后面的复杂度是n/i
所以n / 1 + n / 2 + n / 3 + ... = O(nlogn)
//File Name: nod1251.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月08日 星期六 14时39分39秒 #include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#define LL long longusing namespace std;const int MAXN = 200000 + 10;const int MOD = (int)1e9 + 7;LL jie[MAXN],inv[MAXN];LL qp(LL x,LL y){ LL res = 1; for(;y;y>>=1){ if(y & 1) res = res * x % MOD; x =x * x % MOD; } return res;}void init(){ jie[0] = 1; for(int i=1;i<MAXN;i++) jie[i] = jie[i-1] * i % MOD; for(int i=0;i<MAXN;i++) inv[i] = qp(jie[i],MOD - 2);}LL solve(int n,int m){ if(m == 1) return 1; LL ans = 0,tmp; for(int i=1,ma;i<=n;i++){ ma = (n - i) / i; for(int j=0;j<=ma;j++){ if(m - 1 < j) continue; tmp = jie[n-(j+1)*i+m-2]*inv[m-2]%MOD*inv[n-(j+1)*i]%MOD; tmp = tmp*jie[m-1]%MOD*inv[j]%MOD*inv[m-1-j]%MOD; if(j & 1) ans = (ans - tmp + MOD) % MOD; else ans = (ans + tmp) % MOD; } } return ans * m % MOD;}int main(){ init(); int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d %d",&n,&m); printf("%lld\n",solve(n,m)); } return 0;}
51nod 1668
推下dp公式，矩阵乘法
//File Name: nod1668.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月04日 星期二 16时04分05秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#include <vector>#define LL long longusing namespace std;const int N = 4;const int MOD = (int)1e9 + 7;int g[5];struct matrix_t{ LL x[N+1][N+1]; matrix_t(int v = 1){ memset(x,0,sizeof x); for(int i=1;i<=N;i++) x[i][i] = v; } matrix_t operator*(const matrix_t &r){ matrix_t p(0); for(int k=1;k<=N;k++){ for(int i=1;i<=N;i++){ if(x[i][k] == 0) continue; for(int j=1;j<=N;j++){ (p.x[i][j] += x[i][k] * r.x[k][j] % MOD) %= MOD; } } } return p; } matrix_t power(LL p){ matrix_t r(1),a = *this; for(;p;p>>=1){ if(p & 1) r = r * a; a = a * a; } return r; }};LL solve(LL n){ g[1] = 2,g[2] = 4,g[3] = 7,g[4] = 12; if(n <= 4) return g[n]; matrix_t mat(0); mat.x[1][1] = mat.x[1][2] = mat.x[1][4] = 1; mat.x[2][1] = mat.x[3][2] = mat.x[4][3] = 1; mat = mat.power(n - 4); LL ans = mat.x[1][1] * g[4] % MOD + mat.x[1][2] * g[3] % MOD + mat.x[1][3] * g[2] % MOD + mat.x[1][4] * g[1] % MOD; return ans % MOD;}int main(){ LL n; cin >> n; cout << solve(n) << endl; return 0;}
51nod 1309
求出a中不同的排列有P种
考虑每个数ai会在哪些排列中产生贡献，设a中比M大的数有k个，一个小于等于M的数ai能产生贡献当且仅当ai在排列中的位置在这k个数之前，即对于这k+1个数，ai的位置在最前，由于ai 与这k个数都不相同，这样的概率是1 / (k+1) ,所以ai可以产生贡献的排列有P / (k+1) 个，设a中 <= M 的数的和是S，则答案是
S * P / (k + 1)
先统计出来，对于每一个询问，2分得到答案
//File Name: nod1309.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月05日 星期三 13时22分11秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#include <map>#define LL long long#define fir first#define sec secondusing namespace std;const int MAXN = 50010;const int MOD = (int)1e9 + 7;int a[MAXN];map<int,LL> pre_s,ans;map<int,int> pre_num;LL P,jie[MAXN];LL qp(LL x,LL y){ LL res = 1; for(;y>0;y>>=1){ if(y & 1) res = res * x % MOD; x = x * x % MOD; } return res;}int bs(int l,int r,int x){ if(a[l] > x) return -1; if(a[r] <= x) return a[r]; while(r - l > 1){ int mid = l + r >> 1; if(a[mid] <= x) l = mid; else r = mid; } return a[l];}void solve(int n,int q){ jie[0] = 1; for(int i=1;i<MAXN;i++) jie[i] = jie[i-1] * i % MOD; sort(a,a+n); P = jie[n]; for(int i=0;i<n;i++){ pre_s[a[i]] += a[i]; pre_num[a[i]]++; } for(map<int,int>::iterator it=pre_num.begin();it!=pre_num.end();it++) P = P * qp(jie[it->sec],MOD - 2) % MOD;// cout << P << endl; for(map<int,int>::iterator pre=pre_num.begin(),it;pre!=pre_num.end();pre++){ it = ++pre; --pre; if(it==pre_num.end()) break; pre_num[it->fir] += pre_num[pre->fir];// cout << it->fir << " " << pre_num[it->fir] << endl; } for(map<int,LL>::iterator pre=pre_s.begin(),it;pre!=pre_s.end();pre++){ it = ++pre; --pre; if(it == pre_s.end()) break; (pre_s[it->fir] += pre_s[pre->fir]) %= MOD;// cout << it->fir << " " << pre_s[it->fir] << endl; } for(int i=0;i<n;i++){ ans[a[i]] = pre_s[a[i]] * P % MOD * qp(n-pre_num[a[i]]+1,MOD - 2) % MOD;// cout << a[i] << " " << pre_s[a[i]] << " " << n - pre_num[a[i]] + 1 <<endl; } for(int i=0,x;i<q;i++){ scanf("%d",&x); x = bs(0,n-1,x);// cout << x << endl; if(x == -1) puts("0"); else printf("%lld\n",ans[x]); } }int main(){ int n,q; scanf("%d %d",&n,&q); for(int i=0;i<n;i++) scanf("%d",a + i); solve(n,q); return 0;}
51nod 1667
把甲的数字写成Li+xi的形式，乙的写成Ri-yi的形式，整理后发现，其实要求的是：
x1 + x2 + ... + xn < S ，0 <= xi <= MAi 这种形式，S和MAi都是常数
容斥就可以了
//File Name: nod1667.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月04日 星期二 20时22分27秒 #include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#define LL long longusing namespace std;const int MOD = (int)1e9 + 7;const LL INF = 1000000000000;int l[20],r[20],k1,k2;LL A,inv[20],ma[20];LL qp(LL x,LL y){ LL res = 1; for(;y>0;y>>=1){ if(y & 1) res = res * x % MOD; x = x * x % MOD; } return res;}LL C(LL x,LL y){ if(x < y || y < 0) return 0; if(y == 0 || y == x) return 1; LL res = 1; for(LL i=0;i<y;i++) res = res * (x - i) % MOD * inv[y-i] % MOD;// cout << x << " " << y << endl;// cout << res << endl; return res;}LL cal(int n){ if(A < 0) return 0; LL res = 0,s,tmp; for(int i=0,num;i<(1<<n);i++){ num = 0,s = 0; for(int j=0;j<n;j++){ if(i & (1<<j)){ num++; s += ma[j] + 1; } } tmp = C(A-s+n-1,n-1); if(num & 1) (res = res - tmp + MOD) %= MOD; else (res += tmp) %= MOD; }// if(res < 0) cout << "fff " << endl; return res;}void solve(){ LL ansl = 0,ansg = 0,anseq = 0,sum = 1; A = 0; for(int i=0;i<k1;i++) A -= l[i]; for(int i=k1;i<k1+k2;i++) A += r[i]; anseq = cal(k1+k2); A--; ansl = cal(k1+k2+1); A = 0; for(int i=0;i<k1;i++) A += r[i]; for(int i=k1;i<k1+k2;i++) A -= l[i]; A--; ansg = cal(k1+k2+1); for(int i=0;i<k1+k2;i++){ sum = sum * (r[i] - l[i] + 1) % MOD; } sum = qp(sum,MOD - 2); ansl = ansl * sum % MOD; ansg = ansg * sum % MOD; anseq = anseq * sum % MOD; printf("%lld %lld %lld\n",ansg,anseq,ansl);}int main(){ for(int i=1;i<20;i++) inv[i] = qp(i,MOD - 2); int t; scanf("%d",&t); while(t--){ scanf("%d",&k1); for(int i=0;i<k1;i++) scanf("%d %d",&l[i],&r[i]),ma[i] = r[i] - l[i]; scanf("%d",&k2); for(int i=k1;i<k1+k2;i++) scanf("%d %d",&l[i],&r[i]),ma[i] = r[i] - l[i]; ma[k1+k2] = INF; solve(); } return 0;}
51nod 最近刷题 简要题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。