2024.7.17

标签：itn oo 17 2024.7 int long constexpr mod

2024.7.17 【我们必须知道，我们必将知道】

Wednesday 六月十二

---

P5999 [CEOI2016] kangaroo

//2024.7.17
//by white_ice
//P5999 [CEOI2016] kangaroo
#include<bits/stdc++.h>
using namespace std;
#define itn long long 
#define int long long
constexpr int oo = 4003;
constexpr int mod = 1000000007;

itn n;
int s,t;

itn f[oo][oo];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin >> n >> s >> t;
	f[1][1] = 1;
	for (int i=2;i<=n;i++){
		for (itn j=1;j<=n;j++){
			if (i==s||i==t){
				f[i][j] = (f[i-1][j-1]+f[i-1][j])%mod;
				continue;
			}
			itn res = (i>s)+(i>t);
			f[i][j] += f[i-1][j-1]*(j-res);
			f[i][j] += f[i-1][j+1]*j;
			f[i][j]%=mod;
		}
	}
	cout << f[n][1]%mod;
	return 0;
}

第一次做这种块状DP的题，

也并不是很难

题目解法还是挺新颖的

看来以后要多接触这种新出现的题型，

至少不能听都没听过

然后就是模数写错了调了好久

吃一堑：有模数的题错了先考虑一下模数是不是打错了

---

P3214 [HNOI2011] 卡农

//2024.7.17
//by white_ice
//P3214 [HNOI2011] 卡农
#include<bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long 
constexpr int oo = 1000006;
constexpr int mod = 100000007;

itn n;
itn m;

itn a[oo];
itn k[oo];
itn f[oo];

itn qpow(itn x,itn b){
    int out=1;
    x%=mod;
    for (;b;b>>=1,(x*=x)%=mod)
        if(b&1)
            (out*=x)%=  mod;
    return out;
}
signed main(){
  //  ios::sync_with_stdio(0);
//    cin.tie(0),cout.tie(0);
    cin >> n >> m ;
    a[0] = 1;
    f[0] = 1;
    f[1] = 0;
    k[0] = 1;
    int sum = 1;
    for (itn i=1;i<=n;i++) sum=(sum*2)%mod;
    //sum -= 1;
    for (int i=1;i<=m;i++) a[i]=a[i-1]*(sum-i+mod)%mod;
    for (itn i=1;i<=m;i++)
        k[i]=k[i-1]*i%mod;
    int g = qpow(k[m],mod-2);
    //cout << g;
    for (itn i=2;i<=m;i++)
        f[i] = ((a[i-1]-f[i-1]+mod)%mod-f[i-2]*(i-1)%mod*(sum-i+1+mod)%mod+mod)%mod;

    cout << (f[m]*g)%mod;
    return 0;
}

题目很简单，

从已有的集合中选出m个不同集

要求每个元素被选择的次数为偶数

思路还是比较麻烦的

1. 首先，考虑有序选择i个集合的方案数，记作f[i]

2. 考虑去掉有序性，就是\(\frac{f[i]}{i!}\)

3. 考虑使用其他方式表达出f[i]

\[除去空集，共有2^n-1个集合可选 \]

\[则共A_{2^n-1}^{i-1}种可能 \]

4. 之后考虑去掉空集可能，

不难发现对于这个f[i]，

加入空集并不会产生什么影响

则需减去这f[i-1]种可能

\[A_{2^n-1}^{i-1}-f[i-1] \]

5. 考虑去除重复可能

钦定新加入的第i个与前面第j个重复

则剩余的i-2个为合法方案，

枚举可能出现的前i-1个和可能出现重集的\(2^n-1-(i-2)\)个集合

则

\[f[i] = A_{2^n-1}^{i-1}-f[i-1]-f[i-2]*(i-1)*[2^n-1-(i-2)] \]

6. 得出答案为\(f[m]/m!\)

这里记得求逆元

---

Balanced Subsequences

唯一一道在听课时就听懂的题目

//2024.7.17
//by white_ice
//Balanced Subsequences
#include<bits/stdc++.h>
using namespace std;
#define itn int
constexpr int oo = 4003;
constexpr itn mod = 1000000007;

itn t;
itn n,m,k;
int c[oo][oo];
void getc(){
    for (itn i=0;i<=4000;i++)
        c[i][0] = 1;
    for (itn i=1;i<=4000;i++)
        for (itn j=1;j<=i;j++)
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    getc();

    cin >> t;
while (t--){
    cin >> n >> m >> k;
    if (k>m||k>n){
        cout << 0 << '\n';
        continue;
    }
    cout << (c[n+m][k]+mod-c[n+m][k-1])%mod << '\n';
}
    return 0;
}

关键：找到一个奇妙的小转化

共k对匹配成功，则说明剩余的左右括号，以

\[))))))((((((( \]

这种形式存在，

即提供了n+m-*k个空位

插入合法括号序列即可

---

标签：itn,oo,17,2024.7,int,long,constexpr,mod
From： https://www.cnblogs.com/white-ice/p/18308256