500 :
問題描述：計數問題，滿足下列條件的六面體骰子的數目。。
1：數字範圍在[1，N]之間且兩兩不相同。
2：對面數字和相等且 >= k。
3：經過旋轉相同的篩子被看作是等價的。
…
演算法分析： 枚舉，只要認識到（哪尼），” 任何3對數，只會產生兩組本質不同的解 ” 就可以了。
（room 里有人用DP?.. 是怎麼DP的呢？）
1000 :
問題描述：給定一個長度為 N 的數軸，輸入 M 個三元組 (l, r, d) ，破壞所有 [l, r] 中，被 d 整除的位置？問一共被破壞了多少個位置。
演算法分析：介於 M 值較小，可以用容斥原理做。（線段樹可以馬？）
#include
using namespace std;
int Cn3(int n){
if (n < 3) return 0;
return n * (n-1) * (n-2) / 6;
}
class FoxMakingDiceEasy{
public:
int theCount(int n, int k){
int res = 0, MAX = n * 2 - 5;
// i: 為了計算，枚舉正反兩面的數字和 - 1 的值。
for (int i=k-1;i
#include
#include
using namespace std ;
class BottlesOnShelf
{
public :
long long gcd( long long a , long long b ) { if ( b == 0 ) return a ; return gcd(b , a%b) ; }
long long lcm( long long a , long long b ) { long long c = gcd(a , b) ; return a * b / c ; }
int getNumBroken(int N, vector L, vector R, vector D)
{
int M = L.size() , p , ll , rr , ans ;
long long w , c ;
ans = 0 ;
for ( int i = 1 ; i < (1 << M) ; i ++ )
{
p = 0 ;
for ( int j = 0 ; j < M ; j ++ ) if ( ( i >> j ) & 1 ) p ++ ;
ll = 1 ; rr = N ; w = -1 ;
for ( int j = 0 ; j < M ; j ++ ) if ( ( i >> j ) & 1 )
{
if ( L[j] > ll ) ll = L[j] ;
if ( R[j] < rr ) rr = R[j] ;
if ( w == -1 ) w = D[j] ; else w = lcm(w , (long long)D[j]) ;
}
c = (long long)(rr / w) - (long long)((ll-1) / w) ;
if ( p % 2 == 1 ) ans += c ; else ans -= c ;
}
return ans ;
}
} ;
