滑动窗口（双指针）和求排列数

1.滑动窗口

滑动窗口为在一串序列里面截取满足要求的子串，对于这类问题可以用2个指针来截取数据串。 模板：

for(int i = 0, j = x; i < n; i++) { //j范围有效 & 设计某个性质，使的j具有某种单调性 while(j < m && check(i, j)) jxx //这道题目的具体逻辑 }

例： 输入n和m，n代表序列长度，m代表目标窗口含有1-m，接着输入n个数据。 代码：

#include <iostream> using namespace std; const int N = 1000010, M = 2010; int n, m; int c[N], s[M]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &c[i]); int res = n + 1; int colors = 0; for (int i = 1, j = 0; i <= n; i++) {//i是后，j在前 if (c[i]&&!s[c[i]]) colors++; s[c[i]]++; if (colors == m) { while (!c[j]||s[c[j]] > 1) { s[c[j]]--; j++; } res = __min(res, i - j + 1); } }cout << res << endl; }

2.求排列数

例：求n个数字中取s个的排列（n>=s）和2的n-s方的乘积在mod个10000007. 求排列数有很多方法，这里只举了一个因式分解的简单方法。（n<10^7）

C=n！/s！（n-s）！ 对于每一个阶乘来说，我们都可以把他分解为多个质数的乘积。 所以，对于一个阶乘我们可以先求出1-n的所有质数和其出现的次数。 然后，对于阶乘之间的乘除法就可以转换为幂的加减法。

1-n里有[n/logn]个质数。

求1-n中的质数： 普通方法：从2开始筛，对每一个筛出来的质数，它的倍数肯定不是质数，删掉。 代码：

void get_primes(int n) { for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt++] = i; for (int j = i * 2; j < n; j += i) { st[j] = true; } } } }

线性筛选：从2开始，对每一个筛出来的质数，它的质数倍数肯定不是质数，删掉。 这个方法可以保证每一个数只会被它的最小质因子筛掉一次（因为primes[j]*i的最小质因子为primes[j]） 代码：

void get_primes(int n) { for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt++] = i; for (int j = 0; j < cnt&&i*primes[j]<=n; j ++) { st[primes[j]*i] = true; if (i % primes[j] == 0)break; } } } }

排列数所有代码：

#include <iostream> using namespace std; typedef long long ll; const int N = 2000, mod = 10000007; int primes[N], cnt; //质数数组 int powers[N];//对应质数的个数 bool st[N]; void get_primes(int n) { for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt++] = i; for (int j = 0; j < cnt&&i*primes[j]<=n; j ++) { st[primes[j]*i] = true; if (i % primes[j] == 0)break; } } } } int get(int n, int p) { int s = 0; while (n > 0) { s += n / p; n /= p; } return s; } int main() { int n, s; cin >> n >> s; if (s > n) return 0; else { get_primes(n); int res = 1; for (int i = 0; i < cnt; i++) { int p = primes[i]; powers[i] += get(n, p) - get(s, p) - get(n - s, p); } for (int i = 0; i < cnt; i++) { int p = primes[i]; while (powers[i]--) { res = (ll)res * p % mod; } } for (int i = 0; i < n - s; i++) res = res * 2 % mod; cout << res << endl; } }

结果：