18.10.19 考试总结-白红宇

18.10.19 考试总结

阅读量：5041 次

发布时间：2019-06-12

本文共 5971 字，大约阅读时间需要 19 分钟。

今天又考了zjc大爷的原题然后我惊讶的发现我一道都做不来！！！

真的难受

这道题就是一道在$ac$自动机上面跑得$dp$ 每一次插入一个字符串之后给他的末尾打上标记

在建立$fail$指针的时候标记从他的$fail$传递过来这个标记的作用是表示以这个节点到根节点的串是好的所以在$dp$的时候应该跳过这个串

方程 $dp[i][son[nd][j]] += dp[i - 1][nd] (! ed[nd])$

代码

#include 
     
      using namespace std;typedef long long ll;const int N = 6000 + 5;const ll MOD = 12345;int root = 0, son[N][26], cnt, fail[N], m, n;int dp[N][N];bool ed[N];char s[105];queue
      
       Q;ll fast_pow(ll a, ll b) {        ll ans = 1;    for(;b;b >>= 1, a = a * a % MOD)        if(b & 1) ans = ans * a % MOD;    return ans;}void insert(int len) {        int now = root;    for(int i = 0;i < len;i ++) {        int nd = s[i] - 'A';        if(! son[now][nd]) son[now][nd] = ++ cnt;        now = son[now][nd];    }    ed[now] = true;}void build( ) {        fail[root] = -1;    for(int i = 0;i < 26;i ++) if(son[root][i]) {        fail[son[root][i]] = root; Q.push(son[root][i]);    }    while(! Q.empty( )) {        int u = Q.front( ); Q.pop( );        for(int i = 0;i < 26;i ++) {            if(son[u][i]) {                fail[son[u][i]] = son[fail[u]][i], Q.push(son[u][i]);            }            else son[u][i] = son[fail[u]][i];            }        ed[u] |= ed[fail[u]];    }}void Solve( ) {        build( );    for(int i = 1;i <= m;i ++)        for(int j = 0;j <= cnt;j ++) {            if(ed[j]) continue;            for(int k = 0;k < 26;k ++) {                dp[i][son[j][k]] = (dp[i][son[j][k]] + dp[i - 1][j]) % MOD;            }        }    ll sum = 0;    for(int i = 0;i <= cnt;i ++) if(! ed[i]) sum = (sum + 1ll * dp[m][i]) % MOD;     ll ans = fast_pow(1ll * 26, m);    ans = ((ans - sum) % MOD + MOD) % MOD;    printf("%lld\n", ans);}int main( ) {        freopen("text.in","r",stdin);    freopen("text.out","w",stdout);    scanf("%d%d",& n,& m);    for(int i = 1;i <= n;i ++) {        scanf("%s", s); int len = strlen(s);        insert(len);    }    dp[0][0] = 1;    Solve( );}

本人放弃第二题qwq

这道题是一道双向搜索把和相同的子集划分成两个集合一边值取正另一边取负那么这个时候他们的和为$0$

为了降低复杂度我们把所有数分成两个部分然后一半枚举子集求出他能够到达的所有值的大小

另外一半求出一个大小$sum$之后在之前求出的一半中找$-sum$ 如果有的话答案就加一但是这个时候只能保证正负集合分别在这两个部分但是有可能有元素在正部分中但是应该属于负数部分的

为了避免这种情况在枚举的时候就对这个数进行取负的枚举表示把他分到另外一边集合中

这时候还可能出现子集重复的情况使用装压避免这种情况(为什么迭代器这么快我直接$for$就$T$的好惨)

代码

#include 
     
      #define il inline#define rg registerusing namespace std;typedef long long ll;const int N = 1e7 + 5;const int M = 1e6 + 5;int n, lim, a[M];ll ans;bool vis[N];map

>mp;il int read( ) { int t = 1, ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t;}il void Init( ) { n = read( ); lim = n / 2; for(rg int i = 1;i <= n;i ++) a[i] = read( );}il void dfs(int dep, ll sum, int sta) { if(dep == lim + 1) { mp[sum].push_back(sta); return ; } dfs(dep + 1, sum + 1ll * a[dep], sta | (1 << (dep - 1))); dfs(dep + 1, sum - 1ll * a[dep], sta | (1 << (dep - 1))); dfs(dep + 1, sum, sta);}il void get_ans(int dep, ll sum, int sta) { if(dep == n + 1) { if(mp[-sum].size( )) { vector

:: iterator i; vector

:: iterator j; j = mp[-sum].end( ); for(i = mp[-sum].begin( );i != j;i ++) { int now = sta | * i; if(! vis[now]) {vis[now] = true;} } } return ; } get_ans(dep + 1, sum + 1ll * a[dep], sta | (1 << (dep - 1))); get_ans(dep + 1, sum - 1ll * a[dep], sta | (1 << (dep - 1))); get_ans(dep + 1, sum, sta);}il void Solve( ) { dfs(1, 0, 0); get_ans(lim + 1, 0, 0); for(rg int i = 1;i < (1 << n);i ++) ans += vis[i]; printf("%lld\n", ans);}int main( ) { freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); Init( ); Solve( );}

这道题就是大力推式子...。本人数论学的跟屎一样拜拜了您叻:)

行吧$\sum_{i=0}^{n}(C_{n}^{i})^{2} = C_{2n}^{n}$ 这个就背一背公式什么的..。

首先$iC_{n}^{i} = nC_{n - 1}^{i - 1}$ 可以理解为在$n$个人中选出$i$个人为一只小队在这$i$个人里选出一个队长相当于先在$n$个人里选出一个队长在剩下的人里选$i - 1$个作为队员

所以$E = \sum_{i = 0}^{n}i\cdot C_{n}^{i}p^{i}(1 - p)^{n - i} = n\sum_{i = 0}^{n}C_{n - 1}^{i - 1}p^{i - 1}p^{n - i}\cdot p$

然后中间那一大坨就是二项式定理等于$(p + 1 - p) ^{n - 1} = 1$ 所以$E = np$

然后是下面那个东西把平方打开得到$\sum_{i=0}^{n}(i^{2} + n^{2}p^{2} - 2inp)\cdot p[i]$ 中间的$n^{2}p^{2}$提出去化简和上面是类似的

剩下的$i * i$搞一搞就是$\sum_{i = 0}^{n}i^{2}C_{n}^{i}p^{i}(1 - p)^{n - i} = n\sum_{i = 0}^{n}iC_{n - 1}^{i - 1}p^{i}(1 - p)^{n - i} $

继续化简$n\sum_{i = 0}^{n}iC_{n - 1}^{i - 1}p^{i}(1 - p)^{n - i} = n(\sum_{i = 0}^{n}(i - 1)C_{n - 1}^{i - 1}p^{i}(1 - p)^{n - i}) + p)$

$n(\sum_{i = 0}^{n}(i - 1)C_{n - 1}^{i - 1}p^{i}(1 - p)^{n - i}) + p) = n((n - 1)\sum_{i = 0}^{n}C_{n - 2}^{i - 2}p^{i - 2}(1 - p)^{n - i}\cdot p^{2} + p)$

$n((n - 1)\sum_{i = 0}^{n}C_{n - 2}^{i - 2}p^{i - 2}(1 - p)^{n - i}\cdot p^{2} + p) = n((n - 1)p^{2} + p)$

最后的$-2inp$方法是一样的最后化简得到$np - np^{2}$

代码

#include 
     
      using namespace std;typedef long long ll;const int N = 2 * 1e6 + 5;const ll MOD = 1e9 + 7;int T, n, p;ll fac[N], rfac[N];int read( ) {        int t = 1, ans = 0;    char x; x = getchar( );    while(x < '0' || x > '9') {        if(x == '-') t = -1;        x = getchar( );    }    while(x >= '0' && x <= '9') {        ans = ans * 10 + x - '0';        x = getchar( );    }    return ans * t;}ll fast_pow(ll a, ll b) {        ll ans = 1;    for(;b;b >>= 1, a = a * a % MOD)        if(b & 1) ans = ans * a % MOD;    return ans;}ll C(ll a, ll b) {        if(b > a) return 0;    return fac[a] * rfac[b] % MOD * rfac[a - b] % MOD;}void Init( ) {        scanf("%d",& T); fac[0] = 1; rfac[0] = 1;    for(int i = 1;i < N;i ++) fac[i] = fac[i - 1] * i % MOD;    rfac[N - 1] = fast_pow(fac[N - 1], MOD - 2);    for(int i = N - 2;i >= 1;i --) rfac[i] = rfac[i + 1] * (i + 1) % MOD;}void Solve( ) {        while(T --) {        n = read( ), p = read( );        ll ans = (1ll * n * p % MOD - 1ll * n * p % MOD * p % MOD + MOD) % MOD;        ans = (ans + C(2 * n, n)) % MOD;        printf("%lld\n", ans);    }}int main( ) {        freopen("mathematics.in","r",stdin);    freopen("mathematics.out","w",stdout);    Init( );    Solve( );}

转载于:https://www.cnblogs.com/Rubenisveryhandsome/p/9817510.html

你可能感兴趣的文章