程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Regionals 2014 Asia Xian(幾道簡單題)

Regionals 2014 Asia Xian(幾道簡單題)

編輯:關於C++

 

 

【題意】:

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;
}

Uvalive 7035:

 

【題意】簽到題,求一個序列裡能被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;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved