CH4201 楼兰图腾(树状数组(顺)逆序对)

题目链接:CH4201

对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.

"^"同理.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 200005

typedef long long ll;
typedef unsigned long long ull;

int c[maxn];
int a[maxn];
int Right1[maxn];
int Left1[maxn];
int Right2[maxn];
int Left2[maxn];
int n;

int ask(int x){
  int ans=0;
  for(;x;x-=x&-x) ans+=c[x];
  return ans;
}

void add(int x,int y){
  for(;x<=n;x+=x&-x) c[x]+=y;
}

int main() {
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=n;i>0;--i){
      Right1[i]=n-i-ask(a[i]);
      Right2[i]=ask(a[i]-1);
      add(a[i],1);
  }
  memset(c,0,sizeof(c));
  for(int i=1;i<=n;++i){
    Left1[i]=i-1-ask(a[i]);
    Left2[i]=ask(a[i]-1);
    add(a[i],1);
  }
  ll ans1=0,ans2=0;

  for(int i=1;i<=n;++i){
    ans1+=(ll)Left1[i]*Right1[i];
    ans2+=(ll)Left2[i]*Right2[i];
  } 
  cout<<ans1<<" "<<ans2<<endl;
  return 0;
}

NOI2015/BZOJ4195 -程序自动分析 (并查集+离散化)

题目链接:BZOJ 4195

在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 1000005

typedef long long ll;
typedef unsigned long long ull;

int fa[maxn * 2];

int x1[maxn];
int x2[maxn];
int s[maxn];
int n;
vector<int> b;

void init() {
  b.clear();
  for (int i = 0; i <= 2 * n; ++i) {
    fa[i] = i;
  }
}

int get(int x) {
  if (x == fa[x]) return x;
  return fa[x] = get(fa[x]);
}

void merge(int x, int y) { fa[get(x)] = get(y); }

void discrete() {
  sort(b.begin(), b.end());
  unique(b.begin(), b.end());
}
int query(int x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); }

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    init();
    for (int k = 1; k <= n; ++k) {
      cin >> x1[k] >> x2[k] >> s[k];
      b.push_back(x1[k]);
      b.push_back(x2[k]);
    }
    discrete();
    for (int i = 1; i <= n; ++i) {
      if (s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        merge(x, y);
      }
    }
    int flag = 0;
    for (int i = 1; i <= n; ++i) {
      if (!s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        if (get(x) == get(y)) {
          cout << "NO" << endl;
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      cout << "YES" << endl;
    }
  }
  return 0;
}

BZOJ 1951-古代猪文 (好题,Lucas+CRT+逆元+EXGCD+快速幂)

题目链接:BZOJ 1951

通过欧拉定理的推论得到组合数部分的模数后,用Lucas定理计算,但是模数不是质数,对模数分解质因数后发现所有质因子的指数都是1,于是用中国剩余定理合并方程.具体思路可见《算法竞赛进阶指南》172页.

调了好久,才发现是快速幂的参数写错了.不多说了,直接上代码吧...心态崩了

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int p[4] = {2, 3, 4679, 35617};

int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = exgcd(b, a % b, x, y);
  int z = x;
  x = y;
  y = z - (a / b) * y;
  return d;
}

int quickpow(int n, int m, int mod) {
  int res = 1;
  while (m) {
    if (m & 1) res = (ll)res * n % mod;
    n = (ll)n * n % mod;
    m >>= 1;
  }
  return res;
}

int jc[4][36000];
int factorial() {
  for (int i = 0; i < 4; ++i) {
    jc[i][0] = 1;
    for (int j = 1; j < p[i]; ++j) {
      jc[i][j] = (ll)jc[i][j - 1] * j % p[i];
    }
  }
}

int inv(int a, int mod) {
  int x, y;
  exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}

int lucas(int n, int m, int i) {
  if (n < m) return 0;
  if (n < p[i] && m < p[i])
    return (ll)jc[i][n] * inv(jc[i][n - m] * jc[i][m] % p[i], p[i]) % p[i];
  return (ll)lucas(n / p[i], m / p[i], i) * lucas(n % p[i], m % p[i], i) % p[i];
}

int CRT(int n, int a[], int mod) {
  int res = 0;
  for (int i = 0; i < n; ++i) {
    int M = mod / p[i];
    int t = inv(M, p[i]);
    res = (res + (ll)a[i] * M % mod * t % mod) % mod;
  }
  return res;
}

int A(int n, int i, int a[]) {
  for (int j = 0; j < 4; ++j) {
    a[j] += lucas(n, i, j);
  }
}

int main() {
  int n, g;
  cin >> n >> g;
  const int mod = 999911658;
  if (g == mod + 1) {
    cout << 0 << endl;
  } else {
    factorial();
    int a[4];
    memset(a, 0, sizeof(a));
    for (int i = 1; i * i <= n; ++i) {
      if (n % i == 0) {
        A(n, i, a);
        if (n / i != i) A(n, n / i, a);
      }
    }
    int ans = CRT(4, a, mod);
    ans = quickpow(g, ans, mod + 1);
    cout << ans << endl;
  }
  return 0;
}

POJ 2891 -Strange Way to Express Integers

题目链接: POJ 2891

题意:给出\(n\)对\(a_i,r_i\), 求一个最小正整数\(m\)满足\(m \equiv r_i\pmod a_i\), 或者给出无解.

solution:

\(a_i\)并不保证两两互质, 所以不能用中国剩余定理. 但可以通过数学归纳法, 用拓展欧几里得逐步得出整个线性同余方程组的解.

假设求出前\(k-1\)个方程的一个解\(m\), 记 \(A=lcm( a_1,a_2,...,a_{k-1}) \) ,则 \(m+i*A\) 是通解. 求出满足第\(k\)个方程的\(i\), 就又求出了满足前\(k\)个方程的一个特解.

使用\(n\)次拓展欧几里得算法就能求出整个方程组的解.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll z = x;
  x = y;
  y = z - y * (a / b);
  return d;
}

ll gcd(ll a, ll b) {
  if (!b) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
  int k;
  while (cin >> k) {
    ll a,r;
    cin>>a>>r;
    ll x, y;
    ll A=a;
    exgcd(1, a, x, y);
    x = x%A*r%A;
    int flag = 1;
    for (int i = 1; i < k; ++i) {
      cin>>a>>r;
      if(!flag) continue;
      ll t;
      ll d = exgcd(A, a, t, y);
      if ((r - x) % d != 0) {
        printf("-1\n");
        flag = 0;
        continue;
      }
      t = ( (t* ((r - x) / d)) % a+a )%a ;
      x =x+t*A;
      A = lcm(A, a);
      x=x%A;
    }
    if (flag) cout << x << endl;
  }
  return 0;
}

NOIP2011 -计算系数

题目链接:CH3601

通过逆元计算组合数.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int quickpow(int m,int n,int mod){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*m%mod;
    m=(ll)m*m%mod;
    n>>=1;
  }
  return res;
}

int factorial(int n,int mod){
      if(!n) return 1;
      int res=n%mod;
      while(--n){
        res=(ll)res*n%mod;
      }
      return res;
}

int main() {
  int a,b,n,m,k;
  const int mod=10007;
  cin>>a>>b>>k>>n>>m;
  a=quickpow(a,n,mod);
  b=quickpow(b,m,mod);
  int x=factorial(k,mod);
  int y1=factorial(n,mod);
  int y2=factorial(k-n,mod);
  y1=quickpow(y1,mod-2,mod);
  y2=quickpow(y2,mod-2,mod);
  int ans=(ll)y1*y2%mod*x%mod*a%mod*b%mod;
  cout<<ans<<endl;
  return 0;
}

POJ 1704 -Georgia and Bob

题目链接:POJ 1704

题图:

题图

这题可以转化为NIM博弈.如果棋子为偶数,则从前往后两个两个成对,每对棋子中间的空位看作是一堆石子,多少个空位就多少个石子.如果棋子数为奇数,则在第0个位置加入一个虚拟棋子,然后按偶数情况处理.

容易想到,对于每一对棋子,如果将后面一个棋子往前移,则等效于将该堆石子减少,但将前面一个棋子往前移,则会造成该对棋子中间的空位数增加,就无法和nim对应上.

书上和网上大多数题解提到,如果前面的棋子前移了,后面的棋子相应也往前移相同的单位,则回到了原来的状态,所以前面棋子前移也不影响.

但至于为什么选手就一定会在前面的棋子前移后,将后面的棋子也相应往前移动呢,根据选手总是采取最优策略,我的想法是假设此时选手在原来的状态是必胜的,那么他一定会为了维持这种状态而将后面的棋子相应往前移,而且此时选手不可能是原先状态必败的那个选手,因为必胜的选手不可能会破坏他必胜的状态.而对于必败的选手,那么他无论如何怎么做,都将使对手局面转变为必胜态,或者将前面的棋子往前移,试图破坏目前的状态,可这种破坏是无济于事的,因为前面提到,必胜的选手一定会为了维持他必胜的状态而相应将后面的棋子往前移.至于相邻两对棋子中间的空位,也会由于上述操作亦步亦趋地消除.

(ps:看了一些NIM博弈,感觉只有一开始就处于必胜状态的人,才有所谓的最优策略,此最优策略将带领他胜利,而注定失败的人无论如何挣扎,都将走向失败,哇好残酷啊

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int A[1005];
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> A[i];
    }
    if (n & 1) A[n++] = 0;
    sort(A, A + n);
    int x = 0;
    for (int i = 0; i + 1 < n; i += 2) {
      x ^= (A[i + 1] - A[i] - 1);
    }
    if (x)
      cout << "Georgia will win" << endl;
    else
      cout << "Bob will win" << endl;
  }

  return 0;
}

POJ 2975 -Nim


题目链接:POJ 2975

题意: 问从给定局面,先手有多少种方法使其转换为必败态.

思路:典型的NIM博弈,但不是求谁必胜必败. 检查每个位置是否可以拿走若干个石子使所有堆的异或值为0,即当某一堆的石子数大于其他堆石子数的异或值时,可以通过拿走该堆石子若干,使其与其他堆石子数异或值相等,这样所有堆石子数异或值就为0了,也就是必败态.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int A[1005];

int main() {
  int n;
  while (cin >> n && n) {
    for (int i = 1; i <= n; ++i) {
      cin >> A[i];
    }
    int x = A[1];
    for (int i = 2; i <= n; ++i) {
      x = x ^ A[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      if (A[i] > (A[i] ^ x)) ans++;
    }
    cout << ans << endl;
  }

  return 0;
}

NOIP 2012-同余方程

题目链接 :CH3301

用拓展欧几里得算法求出一组特解\(x_0,y_0\),则\(x_0\)就是原方程的一个解,通解为所有模\(b\)与\(x_0\)同余的整数.题目要求是最小正整数解,可通过取模操作把解的范围移动到\([1,b)\)之间,\([1,b)\)之间的就是最小正整数解.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int exgcd(int a,int b,int &x,int &y){
  if(b==0) {x=1;y=0;return a;}
  int d=exgcd(b,a%b,x,y);
  int z=x;x=y;y=z-y*(a/b);
  return d;
}

int main(){
  int a,b;
  cin>>a>>b;
  int x,y;
  exgcd(a,b,x,y);
  cout<<(x%b+b)%b<<endl; //注意x可能是负数
  return 0;
}

POJ 1845- Sumdiv


题目链接:POJ1845

题意:求\(A^B\)的所有约数之和\(\mod 9901\), \(1 \le A,B \le 5*10^7 \).

把A分解质因数,可以得到约数和为:
\((1+p_1+p_1^2+...+p_1^{B*c_1})*(1+p_2+p_2^2+...+p_2^{B*c_2})*...*(1+p_n+p_n^2+...+p_n^{B*c_n})\)

其中每一项都是等比数列求和:\( \frac{p_i^{B*c_i+1}-1}{p_i-1}\),如果分母逆元存在,则用乘以逆元代替除法运算,如果不存在,有\(p_i\mod 9901=1\),则:
\( 1+p_i+p_i^2+...+p_i^{B*c_i}\equiv 1+1+1^2+...+1^{B*c_i}\equiv B*c_i+1 \pmod {9901} \).

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int c[20],p[20];
int m;
void divide(int a){
    m=0;
    for(int i=2;i<=sqrt(a);++i){
      if(a%i==0){
        p[++m]=i;
        c[m]=0;
        while(a%i==0){
          a/=i;
          c[m]++;
        }
      }
    }
    if(a>1){
      p[++m]=a;
      c[m]=1;
    }
}

int quickpow(int mod,int a,int n){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*a%mod;
    a=(ll)a*a%mod;
    n>>=1;
  }
  return res;
}

int inv(int mod,int x){
  return quickpow(mod,x,mod-2);
}

int main(){
  int a,b;
  const int mod=9901;
  cin>>a>>b;
  divide(a);
  int ans=1;
  for(int i=1;i<=m;++i){
    int x=(quickpow(mod,p[i],(ll)b*c[i]+1)-1+mod)%mod;
    int y=(p[i]-1)%mod;
    if(y){
      ans=(ll)ans*(x*inv(mod,y))%mod;
    }
    else{
      ans=ans*((ll)b*c[i]+1)%mod;  
    }
  }
  cout<<ans<<endl;
  return 0;
}

POJ 3696 -The Luckiest number


题目链接:POJ 3696

题意:给定一个正整数\(L\), \(L \le 2*10^9\). 问至少多少个\(8\)连在一起组成的正整数是\(L\)的倍数?

solution:
\(x\)个\(8\)连在一起组成的正整数可写作\(8(10^x-1)/9\). 题目就是要求出一个最小的\(x\),满足\(L| \frac{8(10^x-1)}{9} \).

设 \(d = gcd(L,8)\),

有\(9L | 8(10^x-1) \Leftrightarrow \frac{9L}{d}|(10^x-1) \Leftrightarrow 10^x \equiv 1 \pmod {\frac{9L}{d}} \)

引理:若正整数\(a,n\)互质,则满足\(a^x\equiv 1 \pmod n\)的最小正整数\(x_0\)是\(\varphi(n)\)的约数(可通过反证法证明)

根据以上,只需求出欧拉函数\(\varphi(\frac{9L}{d})\), 枚举它的所有约数,用快速幂逐一检查是否满足条件即可。

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b) {
  if (!b) return a;
  return gcd(b, a % b);
}

ll getPhi(ll n) {
  ll ans = n;
  for (ll i = 2; i <= sqrt(n); ++i) {
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

ll mul(ll mod, ll a, ll b) {
  ll res = 0;
  while (b) {
    if (b & 1) {
      res = (res + a) % mod;
    }
    a = (a << 1) % mod;
    b >>= 1;
  }
  return res;
}

ll quickpow(ll mod, ll m, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) res = mul(mod, res, m);
    m = mul(mod, m, m);  // 注意:直接乘会溢出!
    n >>= 1;
  }
  return res;
}

int main() {
  ll n;
  int kase = 0;
  while (cin >> n && n) {
    ll t = n / gcd(n, 8) * 9;
    ll p = getPhi(t);
    int flag = 0;
    for (ll i = 1; i <= sqrt(p); ++i) {
      if (p % i == 0) {
        if (quickpow(t, 10, i) == 1) {
          printf("Case %d: %lldn", ++kase, i);
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      for (ll i = sqrt(p); i >= 1; --i) {
        if (p % i == 0) {
          if (quickpow(t, 10, p / i) == 1) {
            printf("Case %d: %lldn", ++kase, p / i);
            flag = 1;
            break;
          }
        }
      }
    }
    if (!flag) printf("Case %d: %dn", ++kase, 0);
  }
  return 0;
}