A simple Blog for wyx I've been down the bottle hoping.
SRM 500 数学 dp
发表于: | 分类: Oi | 评论:0 | 阅读:68

最近做做tc题

好多题好神啊……有的题没有队爷题解可能就GG了

500pts

A和B两人在方格上轮流放检验器。第一次操作A在 $(0,0)$ 放上一个检验器。之后每次操作中,对于空方格 $(x,y)$,满足下列某一条件时在 $(x,y)$ 放上一枚检验器:

  1. $(x−2,y)$ 上有一个对方的检验器,且 $(x−1,y−1)$ 上没有
  2. $(x−1,y−1)$ 上有一个对方的检验器,且 $(x−2,y)$ 上没有检验器
    现在双方轮流一共操作 $t$ 次,问左下角为 $(x0,y0)$,右上角为 $(x0+w−1,y0+h−1)$ 的矩形中的每个方格的状态(空,$A$的检验器或B的检验器)。

从最开始的 $(0,0)$ 开始,下一轮放的棋子必然是上一轮棋子在右上方拓展出来的,新拓展出来的棋子坐标和比原来的大2

那么久非常容易发现如果有$A$的棋子就是4的倍数,否则就是2的倍数但不是4的倍数

现在我们令 $a_{(x,y)}$为 $(x,y)$ 处的状态,有定义可知 $a_{(x,y)} = a_{(x-1,y-1)} xor a_{(x-2,y)}$

那么这个式子可以看成是前后两项的和在模二意义下的

我们令$b_{\frac{x+y}{2},y}=a_{(x,y)}$, 那么显然有$ b_{\frac{x+y}{2},y}=(b_{\frac{x+y}{2}-1,y}+b_{\frac{x+y}{2}-1,y-1}) \mod \ 2$

你会发现这其实是一个杨辉三角23333333

所以问题变成了 $C(n,m)$ 什么时候等于一 $(\mod 2)$

由卢卡斯定理我们知道这个东西可以写成 $\prod C_{a_i}^{b_i}$

$a_i$, $b_i$ 是二进制的每一位

然后容易发现要想要答案 = 1必然每一位都不能等于0

而 只有 $C_0^1 = 0$

也就是说其实在n&m=m的时候其等于1,否则等于0

然后23333333333333333333333


// BEGIN CUT HERE

#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
typedef long long LL;

class CheckerExpansion {
    public:
    LL T;
    char calc(LL x,LL y) {
        if((x+y)&1) return '.';
        LL a = (x+y) >> 1, b = (x-y) >> 1;
        if(a >= T || b < 0 || a < b || (a&y)!=y) return '.';
        return a & 1 ? 'B' : 'A';
    }
    vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) {
        T = t;
        vector <string> res;
        for(int y=h-1;y>=0;--y) {
            string tmp = "";
            for(int x=0;x<=w-1;++x)  tmp = tmp + calc(x0+x,y0+y);
            res.pb(tmp);
        }
        return res;
    }

    
// 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(); }
    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 vector <string> &Expected, const vector <string> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }
    void test_case_0() { long long Arg0 = 1LL; long long Arg1 = 0LL; long long Arg2 = 0LL; int Arg3 = 4; int Arg4 = 4; string Arr5[] = {"....", "....", "....", "A..." }; vector <string> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); verify_case(0, Arg5, resultAfter(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_1() { long long Arg0 = 5LL; long long Arg1 = 4LL; long long Arg2 = 1LL; int Arg3 = 3; int Arg4 = 4; string Arr5[] = {"A..", "...", "B..", ".B." }; vector <string> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); verify_case(1, Arg5, resultAfter(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_2() { long long Arg0 = 1024LL; long long Arg1 = 1525LL; long long Arg2 = 512LL; int Arg3 = 20; int Arg4 = 2; string Arr5[] = {"B...B...B...........", ".B.A.B.A.B.........." }; vector <string> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); verify_case(2, Arg5, resultAfter(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_3() { long long Arg0 = 53LL; long long Arg1 = 85LL; long long Arg2 = 6LL; int Arg3 = 5; int Arg4 = 14; string Arr5[] = {".....", ".....", "B....", ".B.A.", ".....", ".....", ".....", ".....", ".....", ".....", "B....", ".B...", "..B..", ".A.B." }; vector <string> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); verify_case(3, Arg5, resultAfter(Arg0, Arg1, Arg2, Arg3, Arg4)); }

// END CUT HERE

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



850 pts

给定两个相同长度的单词 $w1,w2$ (都只含有' $a$ ',' $b$ ',' $c$ '三种字符)。已知' $a$ '变成' $b$ '(' $b$ '无法直接变成' $a$ ',下同),' $b$ '变成' $c$ ',' $c$ '变成' $a$ '的代价分别为 $c1$,$c2$,$c3$ ,求把 $w1$ 变为 $w2$ 且总代价不超过 $maxCost$ 的方案数。

傻逼dp

我们可以发现一个合法方案必然是先把所有的都变成下面的,然后每次找一个转一圈,那么我们就可以算出操作的次数

$f(i,j,k)$ 表示经过 $i$ 次操作后,有 $j$ 个差一次相同 $j$ 个差两次相同,转移的话就分三种情况讨论一下

这个东西直接跑复杂度是与操作次数线性相关的

然后你需要把这个东西降下来,注意到这个东西相当于图上走 $k$ 步的方案数,直接矩阵乘法一下就好了

最多有 $n^2$ 个状态所以复杂度是 $(n^2)^3 \log{Max}$

#include <bits/stdc++.h>
using namespace std ;
const int N = 300+5;
const int mod = 1e9+7;
typedef long long LL;

int table[N], bel[N];
int change[5][5], n, cnt;

struct Matrix {
    int a[82][82];

    void init () {
        for(int i=0;i<=cnt;++i) for(int j=0;j<=cnt;++j) a[i][j] = (i==j);
    }
}ret, pret, trans;

Matrix& operator *(const Matrix &a,const Matrix &b) {
    memset(ret.a,0,sizeof ret.a);
    for(int i=0;i<=cnt;++i) 
        for(int j=0;j<=cnt;++j) 
            for(int k=0;k<=cnt;++k) 
                ret.a[i][j] = ((LL)ret.a[i][j] + (LL)a.a[i][k]*b.a[k][j])%mod;
    return ret;
}

Matrix &operator ^ (Matrix &a,LL b) {
    pret.init();
    for(;b;b>>=1,a=a*a) {
        if(b&1) {
            pret = pret * a;
        }
    }
    return pret;
}

class ConversionMachine {
public:
    int countAll(string word1, string word2, vector <int> costs, int maxCost) {
        change[0][1] = costs[0], change[1][2] = costs[1], change[2][0] = costs[2];
        change[0][2] = change[0][1] + change[1][2], change[1][0] = change[1][2] + change[2][0], change[2][1] = change[2][0] + change[0][1];
        n = word1.size();
        for(int i=0;i<=n;++i) 
            for(int j=0;j<=n;++j) 
                if(i+j<=n) {
                    table[++cnt] = i*(n+1)+j;
                    bel[i*(n+1)+j] = cnt;
                }
        for(int i=1;i<=cnt;++i){            
            int tmp1 = table[i]/(n+1), tmp2 = table[i] %(n+1), tmp3 = n - tmp1 - tmp2;
            if(tmp1) trans.a[i][bel[(tmp1-1)*(n+1)+tmp2]] += tmp1;
            if(tmp2) trans.a[i][bel[(tmp1+1)*(n+1)+tmp2-1]] += tmp2;
            if(tmp3) trans.a[i][bel[tmp1*(n+1)+tmp2+1]] += tmp3;
        }
        trans.a[bel[0]][++cnt] = 1, trans.a[cnt][cnt] = 1;
        int tmp1 = 0, tmp2 = 0, steps = 1;
        for(int i=0;i<n;++i) {
            int tt = (word2[i]-word1[i]+3)%3;
            maxCost -= change[word1[i]-'a'][word2[i]-'a'];
            if(maxCost < 0) return 0;
            steps += tt;
            if(tt == 1) tmp1 ++;
            else if(tt==2) tmp2 ++;
        }
        steps += (maxCost)/(LL)(costs[0]+costs[1]+costs[2]) * 3;
        trans = trans ^ steps;
        return trans.a[bel[tmp1*(n+1)+tmp2]][cnt];
    }
 
    
// 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(); }
    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() { string Arg0 = "a"; string Arg1 = "b"; int Arr2[] = {100,2,3}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 205; int Arg4 = 2; verify_case(0, Arg4, countAll(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_1() { string Arg0 = "abcba"; string Arg1 = "abcba"; int Arr2[] = {67,23,43}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 0; int Arg4 = 1; verify_case(1, Arg4, countAll(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_2() { string Arg0 = "cccccccc"; string Arg1 = "aaaaaaaa"; int Arr2[] = {10000000,1,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 100; int Arg4 = 40320; verify_case(2, Arg4, countAll(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_3() { string Arg0 = "aa"; string Arg1 = "cc"; int Arr2[] = {1,10,100}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 1787; int Arg4 = 123611681; verify_case(3, Arg4, countAll(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main(){
    ConversionMachine ___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