Regionals 2014 Asia Xian(幾道簡單題)

Regionals 2014 Asia Xian(幾道簡單題)

【題意】：

n個格子排成一行，有m種顏色，問用恰好k種顏色進行染色，使得相鄰格子顏色不同的方案數。
k≤106n,m≤109
【思路】：組合+逆元+容斥
首先，我們可以從m個顏色中取出k個，即Ckm。
接著容易想到 $k(k-1)^{n-1},這個是使用不超過k種顏色的所有方案。但我們要求的是恰好使用k種顏色。
假設選出的k種顏色標號為1，2，3，...,k，那麼記A_i$ 為不使用顏色i的方案數，求的就是 |S|−|A1?A2???An| 。也就是反過來考慮，我們不考慮用了哪些顏色，我們考慮哪些顏色沒用！減去所有有沒使用顏色的方案的並集，剩下的方案就是使用了所有k種顏色的方案。上式中的 |S| 即 $k(k-1)^{n-1}，後者就可以用容斥原理來求了。注意到我們只是給顏色標了個號，所以後面每一項的應為C^i_k(k-i)(k-i-1)^{n-1}$ 的形式，即選出i個不使用的顏色，用剩余顏色去塗的方案數。

代碼：

/*
* Problem: Uvalive No.7040
* Running time: 1.916MS
* Complier: C++
* Author: javaherongwei
* Create Time:   20:10 2015/9/6 星期日
*
*/
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
const LL MOD = 1e9+7;
const LL N = 1e6+10;

LL C[N],inv[N];
LL n,m,k;

LL pow_mod(LL a,LL b)
{
    LL res=a,ans=1;
    while(b)
    {
        if(b&1) ans=ans*res%MOD;
        res=res*res%MOD;
        b>>=1;
    }
    return ans;
}

inline LL get_inverse(LL x)
{
    return pow_mod(x,MOD-2);
}

void init()
{
    for(LL i=1; i=1; --i)
        {
            f1=(f1+f2*calc(i)+MOD)%MOD;
            f2=-f2;
        }
        ans_mk=ans_mk*f1%MOD;
        printf(Case #%d: ,tot++);
        printf(%lld
,ans_mk);
    } return 0;
}

【題意】簽到題，求一個序列裡能被3整除的數的個數

代碼：

/*
* Problem: Uvalive No.7035
* Running time: 0.010MS
* Complier: C++
* Author: javaherongwei
* Create Time:   20:20 2015/9/6 星期日
*/

#include 
using namespace std;
const int N=1e6+10;
int arr[N];
int main()
{
    int t,tot=1;scanf(%d,&t);
    while(t--)
    {
        int s=0,n;
        scanf(%d,&n);
        for(int i=0; i

Uvalive 7045: (gcd+模擬)
 
代碼：
 
/*
* Problem: Uvalive No.7045
* Running time: 0.010MS
* Complier: C++
* Author: javaherongwei
* Create Time:   20:20 2015/9/6 星期日
*/
#include 
using namespace std;
typedef long long LL;
LL n,m,k,a,b,c,ans;
void get(LL a,LL b)
{
    if(b)
    {
        ans+=a/b;
        get(b,a%b);
    }
}
int main()
{
  int t,tot=1;scanf(%d,&t);
  while(t--)
  {
      scanf(%lld %lld,&a,&b);
      printf(Case #%d: ,tot++);
      if(a==b&&b==0)
      {
          puts(1);
          continue;
      }
      if(a!=b&&(a==0||b==0))
      {
          puts(2);
          continue;
      }
      if(max(a,b)-min(a,b)==min(a,b))
      {
          puts(3);
          continue;
      }
      ans=0;
      get(a,b);
      printf(%lld
,ans+1);
  } return 0;
}