• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

代码强制循环# 785(第2部分)[D-E]解决方案


Recommended Posts

目录d .丢失等差数列题目主旨代码e .幂还是异或?主题思想代码

D. Lost Arithmetic Progression

题目大意

A,B是两个有限长的等差数列,C是另一个算术级数,由同时出现在A和B中的元素组成

现在给定B和C的第一项\(f_b,f_c\)、容差\(d_b,d_c\)和长度\(l_b,l_c\),A有多少种可能的解?

注意:

当有无穷多个时,输出-1。

答案需要取模\(1e9 7\)

思路

显然,C的容差\(d_c\)是A和B的容差的最小公倍数,即\(d_c=\text{lcm}(d_a,d_b)\。

首先讨论一下什么时候是\(0\)。

b的第一项需要小于c的第一项:\(f_b \le f_c\)

b的最后一项需要大于c的最后一项:\(f _ b d _ b \ times(l _ b-1)\ ge f _ c d _ c \ times(l _ c-1)\)

c的容差需要能被b的容差整除:\(d_b|d_c,d_c\%d_b=0\)

C的第一项需要被B包含(这样以后总会被包含):\((f_c-f_b) \% d_b=0\)

然后讨论什么时候是\(-1\)。无限个例只跟第一个和最后一个有关。

当\(f_c-d_c f_b\)或\ (f _ c l _ c \乘以d _ c f _ b (l _ b-1) \乘以d _ b \)。那么等差数列\(A\)可以无限延伸。

如果等于就不行了,比如说:\(f_c-d_c=f_b\),这样向左延伸的\(A\)一定会遇到\(f_b\),所以不能无限延伸。

剩下的我们只需要枚举\(d_a\)并保证\(d_a\)是\(d_c\)和\(\text{lcm}(d_a,d_b)=d_c\)的一个因子。认为

代码

#包含位/标准数据。h

const int mod=1e 9 7;

使用ll=long long

ll添加(ll a,ll b){

return(a b)% mod;

}

ll mul(ll a,ll b){

返回a * b % mod

}

ll gcd(ll a,ll b){

而(b^=a^=b^=a%=b);

返回a;

}

ll lcm(ll a,ll b){

返回a * b/gcd(a,b);

}

void solve(){

ll fb、db、lb、fc、dc、LC;

std:cin fb db lb

std:cin fc dc lc

//检查0

if(FB fc | | FB db *(l b-1)fc DC *(LC-1)| | DC % db!=0 || (fc - fb) % db!=0){

STD : cout 0“\ n”;

返回void();

}

//检查1

if(FB fc-DC | | FB db *(l b-1)fc DC * LC){

STD : cout-1“\ n”;

返回void();

}

ll ans=0;

//枚举dc的因子

for(ll da=1;da * da=dcda){

if (dc % da!=

0) continue; if (lcm(da, db) == dc){ ll tmp = mul(dc / da, dc / da); ans = add(ans, tmp); } if (da * da != dc && lcm(dc / da, db) == dc){ ll tmp = mul(da, da); ans = add(ans, tmp); } } std::cout << ans << "\n"; } int main(){ std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1; std::cin >> t; while (t--) solve(); return 0; }

E. Power or XOR?

题目大意

给你一个长度为\(n\)序列\(\{B\}\)和一个整数\(k\)。存在另一个序列\(\{A\}, A_i = 2^{B_i}\)。存在一个多义表达式\(E= A_1 \and A_2 \and \cdots \and A_n\),保证其中的\(\and\)至少有\(k\)个代表\(\oplus\),其余的代表\(\texttt{power}\)。现在,要求你求解出所有可能的\(E\)的值,并输出他们的异或(\(\oplus\))。需要注意的是,结果可能很大,所以我们需要在结果上取模\(2^{2^{20}}\)。

  • \(1\le n \le 2^{20}, 0 \le k < n\)
  • \(1 \le B_i < 2^{20}\)

思路

Hint1
我们可以发现,A中所有的元素,无论是否取Mod都是2的幂级数。 Hint2
我们只需要分别考虑某个区间全为Power的贡献。 Hint3
由于Module=2^2^20,所以我们最多只需要考虑区间长度为20即可。

依据上面几个提示,我们进一步探究某个区间\([l, r]\)。我们假设区间\([l, r]\)中都是power符号。那么显然,假设这个区间仅存在一次,它对答案的贡献为:\(2^{B_l \times \Pi _{i=l+1}^{r}A_{i}}\)。当\(B_l \times \Pi_{i=l+1}^{r} \ge 2^{20}\)时,它将不再对答案做出贡献,这是因为它会被Module掉,同时也是这个性质保证了我们答案的时间复杂度。

但是, 除了单独的分析任意一个区间所做的贡献,我们还需要考虑这个区间在多少个可能的\(E\)中出现过。据题目大意中知,我们有尚未使用的任意符号\(m = (n-1) - (r-l) - 2/1/0\),以及尚未使用的\(\oplus\)符号\(q = k - 2/1/0\)。其中,\(2/1/0\)分别代表:正常,左右其中一侧在corner,以及两边都在corner。

因此,区间\([l, r]\)出现的次数为:\(cnt = \tbinom{m}{q} + \tbinom{m}{q+1} + \cdots + \tbinom{m}{m}\),这并不太好计算,但是由于我们需要求的是异或,因此我们只关心\(cnt\)的奇偶性。那么问题回到如何快速判断组合数的奇偶性?显然,暴力计算不符合时间要求。

1. Lucas Theorem

我们将简单介绍下,什么是卢卡斯定理(Lucas Theorem),卢卡斯定理主要是用于求解大组合数取模的问题,其中模数\(p\)必须为素数。

\[\binom{n}{m}\bmod p=\binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n\bmod p}{m\bmod p} \bmod p \]

边界条件为,当\(m=1\)时,返回\(0\)。现在,我们已经有了卢卡斯定理,我们略过其证明过程(有兴趣的可以参考Oi-wiki,也就是那个链接),利用其快速判断组合数的奇偶性。

2. 组合数判断奇偶性

给定任意的\(x, y\),存在:

\[\binom{y}{x} \bmod 2 = \binom{z}{0} \times \prod_{k_1} \binom{1}{0} \times \prod_{k_2} \binom{1}{1} \times \prod_{k_3} \binom{0}{0} \times \prod_{k} \binom{0}{1} \mod 2 \]

其中只有\(\tbinom{0}{1} = 0\),其余的都为\(1\),因此我们只需要判断是否存在\(\tbinom{0}{1}\)即可,如果存在则为偶数否则为奇数。

考虑到卢卡斯定理求解中,由于\(p=2\),实际上我们在分别对数字\(x,y\)的每一位进行处理,因此当且仅当\(x\)中任何\(bit\)为\(1\)时\(y\)中对应的\(bit\)也为\(1\)。最终,我们可以用位运算的形式简洁的判断组合数\(\binom{y}{x}\)的奇偶性:\((x\& y)=x\)。

// input x, y
if ((x & y) == x) return "奇数";
else return "偶数"

如上,我们已经证明了如何快速计算组合数的奇偶性,现在我们只需要逐步处理即可。

代码

const int N = 1 << 20;
void solve(){
    int n, k;
    std::cin >> n >> k;
    vt<int> b(n);
    rep (i, 0, n) std::cin >> b[i];
    vt<vt<int>> odevity(n + 1, vt<int> (3, -1));
    auto getparity = [&](int nouse, int nooplus){
        int useoplus = k - nooplus;
        if (odevity[nouse][useoplus] == -1){
            int x = 0;
            for (int cur = nooplus; cur <= nouse; ++ cur){
                x ^= ((nouse & cur) == cur);
            }
            odevity[nouse][useoplus] = x;
        }
        return odevity[nouse][useoplus];
    };
    vt<int> ans(N, 0);
    for (int l = 0; l < n; ++ l){
        ll len = 1;
        for (int r = l; r < n; ++ r){
            if (r == l) len *= b[r];
            else {
                if (b[r] > 20) break;
                len <<= b[r];
                if (len > N) break;
            }
            int nouse = n - 1 - (r - l) - 2;
            int nooplus = k - 2;
            if (l == 0) ++ nouse, ++ nooplus;
            if (r == n - 1) ++ nouse, ++ nooplus;
            ans[len] ^= getparity(nouse, nooplus);
        }
    }
    // if ans == 0 can't pop it 
    while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
    std::reverse(all(ans));
    for (auto x: ans) std::cout << x;
    std::cout << "\n";
}
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now