A simple Blog for wyx I've been down the bottle hoping.
SRM 555 构造 组合数学 容斥
发表于: | 分类: Oi | 评论:0 | 阅读:65

SRM T2 555pts

有一个 $W\times H$ 的表格,初始时每个位置上都是0

一次操作可以把一行进行0,1翻转,也可以吧一列0,1翻转,现在告诉你对行进行的次数以及对列进行的次数,求有多少个方案使得图中恰好有 $S$ 个1

两种方案不同当且仅当至少有一行或一列被操作的次数不同.

自己画一下,你会发现假设对行操作的次数是 $a$, 对列操作实际次数是 (这里的实际操作指的是真的从0变成1而没有再变回去)

那么显然图中1的个数是 $a\times(H-b)+b\times(W-a)$

然后我们枚举 $a$, 通过上面的式子算出 $b$ ,然后算方案就行了

加入有剩下的步数,组合数算一下就行了

#include <bits/stdc++.h>
const int N = 3000;
using namespace std ;
const int mod = 555555555;
typedef long long LL;

LL C[2500+5][2500+5];

inline void init() {
    for(int i=0;i<=2500;++i) {
        C[i][0] = 1;
        for(int j=1;j<=i;++j) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
        }
    }
}

class XorBoard
{
    public:
    int count(int H, int W, int Rcount, int Ccount, int S)
    {
        init();
        LL ans = 0;
    //  return 1;
        for(int i=Rcount&1;i<=H && i<=Rcount;i+=2) {
            for(int j=Ccount&1;j<=W && j<=Ccount;j+=2) {
                if(i*(W-j)+j*(H-i)== S) {
                    (ans += (LL) C[H][i] * C[W][j] % mod * C[(Rcount-i)/2+H-1][H-1] % mod * C[(Ccount-j)/2+W-1][W-1]%mod) %= mod;
                }
            }
        }
        return (int) ans % mod;
    }
 
    
// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 2; int Arg3 = 2; int Arg4 = 4; int Arg5 = 4; verify_case(0, Arg5, count(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_1() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 0; int Arg3 = 0; int Arg4 = 1; int Arg5 = 0; verify_case(1, Arg5, count(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_2() { int Arg0 = 10; int Arg1 = 20; int Arg2 = 50; int Arg3 = 40; int Arg4 = 200; int Arg5 = 333759825; verify_case(2, Arg5, count(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_3() { int Arg0 = 1200; int Arg1 = 1000; int Arg2 = 800; int Arg3 = 600; int Arg4 = 4000; int Arg5 = 96859710; verify_case(3, Arg5, count(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_4() { int Arg0 = 555; int Arg1 = 555; int Arg2 = 555; int Arg3 = 555; int Arg4 = 5550; int Arg5 = 549361755; verify_case(4, Arg5, count(Arg0, Arg1, Arg2, Arg3, Arg4)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
    XorBoard ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

T3 1055 pts

容斥,我们先枚举一下每个位置进行模拟,模拟出在这个位置开始是否会超出界限,如果不超过界限,我们把被修改的位置标记下来,这些位置可以随便是什么,剩下的位置则必须和给定的第一个串相同。然后我们枚举一下当前的所有位置,得到他随便得的位置集合,然后找到之前所有的和他相交的集合,容斥方案数即可

#include <bits/stdc++.h>
typedef long long LL;
using namespace std ; 
LL a[40+5], b[40+5], ans, c;
LL n, m, top, cnt;
string s;
void check(string s) {
    for(int i=0;i<n;++i) if(b[i] != -1 && b[i] != s[i] - '0') return ;
    a[cnt] = 0; for(int i=0;i<n;++i) if(b[i] != -1) a[cnt] |= 1ll<<i;
}

inline int calc(LL x) {
#define lowbit(x) ((x)&(-x))
    int ans = 0;
    while(x) {
        ans ++;
        x -= lowbit(x);
    }
    return ans;
}

class MapGuessing
{
    public:
    long long countPatterns(string goal, vector <string> code)
    {
        LL stack[45] = {};
        for(int i=0;i<code.size();++i) s = s + code[i];
        n = goal.size(), m = s.size();
        for(int i=0;i<n;++i) {
            a[++cnt] = 0;
            memset(b,-1,sizeof b);
            for(int j=0,now=i;j<m;++j) {
                if(s[j] == '<') now --;
                else if(s[j] == '>') now ++;
                else b[now] = s[j] - '0';
                if(now < 0 || now >= n) {
                    cnt --;
                    break;
                }
                check(goal);
            }
        }
        if(cnt) ans = 1;
        for(int now=1;now<=cnt;++now) {
            top = 0;
            for(int i=1;i<now;++i) if(a[i] & a[now]) stack[++top] = i;
            for(int i=0;i<1<<top;++i) {
                c = a[now];int sum = 0;
                for(int j=0;j<top;++j) if((1<<j)&i) c &= a[stack[j+1]], sum ++;
                if(sum & 1) ans -= (1ll<<calc(c))-1;
                else ans += (1ll<<calc(c))-1;
            }
        }
        return ans;
    }
    
// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { string Arg0 = "000"; string Arr1[] = {"0"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 4LL; verify_case(0, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_1() { string Arg0 = "001"; string Arr1[] = {"0>1"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 5LL; verify_case(1, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_2() { string Arg0 = "000"; string Arr1[] = {"1>1>1"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 1LL; verify_case(2, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_3() { string Arg0 = "11001"; string Arr1[] = {">><<<<><<"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 0LL; verify_case(3, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_4() { string Arg0 = "1000101011"; string Arr1[] = {"1<<0>>0>1"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 22LL; verify_case(4, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_5() { string Arg0 = "00000010000000000000000000000000"; string Arr1[] = {"><>>0<0<>>1>0><>", "<<0>>0<>><0>0>>><><", ">>>0<>", ">0><>>>>0<<><>>0>>>0<0>>0>"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 13601LL; verify_case(5, Arg2, countPatterns(Arg0, Arg1)); }
    void test_case_6() { string Arg0 = "11100011010111111010100100110001101"; string Arr1[] = {"11111111111111111111"
,"1<><><><><><><><><>1"
,"1<>000>000><0<><0<>1"
,"1<0<><>0><0<00>00<>1"
,"1<>00<>000><0<0<0<>1"
,"1<><>0>0><0<0<><0<>1"
,"1<000<>0><0<0<><0<>1"
,"1<><><><><><><><><>1"
,"1<>000><000<>000><>1"
,"1<>0><><0<><>0><><>1"
,"1<>000><000<>000><>1"
,"1<><>0><><0<><>0><>1"
,"1<>000><000<>000><>1"
,"1<><><><><><><><><>1"
,"11111111111111111111"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 90LL; verify_case(6, Arg2, countPatterns(Arg0, Arg1)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
    cout << t.countPatterns("000000000000000000000000000000000000", {"0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0", ">0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0>0"}) << endl;
    return 0;
    MapGuessing ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP