【BZOJ 4197】[NOI2015] 寿司晚宴

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4197

解题报告

考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$

Code

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

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
	a = (a + b) % MOD;
}

inline int num(int x, int t) {
	for (; t; x /= 3, t--);
	return x % 3;
}

inline int SET(int w, int t, int v) {
	static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
	int ret = 0;
	for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
		if (t & 1) {
			ret += buf[i] * v;
		} else {
			ret += buf[i] * (w % 3);
		}
	}
	return ret;
}

int main() {
	freopen("dinner.in", "r", stdin);
	freopen("dinner.out", "w", stdout);
	cin>>n>>MOD; 
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 8; j++) {
			int t = num(i, j);
			if (t == 1) {
				sta1[i] |= 1 << j;
			} else if (t == 2) {
				sta2[i] |= 1 << j;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << 8); j++) {
			for (int k = 1; k <= 2; k++) {
				tt[i][j][k] = SET(i, j, k);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		gpri[i] = i;
		for (int j = 0; j < 8; j++) {
			if (gpri[i] % pri[j] == 0) {
				spri[i] |= (1 << j);
				while (gpri[i] % pri[j] == 0) {
					gpri[i] /= pri[j];
				}
			}
		}
	}
	f = arr1, g = arr2, h = arr3;
	g[0] = f[0] = 1;
	for (int i = 2; i <= n; i++) {
		if (gpri[i] == 1) {
			for (int j = M - 1; ~j; j--) {
				if (g[j]) {
					int sta = 0;
					for (int k = 0; k < 8; k++) {
						if (spri[i] >> k & 1) {
							sta |= num(j, k);
						}
					}
					if (sta == 0) {
						relax(f[tt[j][spri[i]][1]], g[j]);
						relax(f[tt[j][spri[i]][2]], g[j]);
					} else if (sta < 3) {
						relax(f[tt[j][spri[i]][sta]], g[j]);
					}
				}
			}
			memcpy(g, f, sizeof(arr1));
			swap(f, g);
		} else {
			sta[gpri[i]].push_back(spri[i]);
		}
	}
	for (int i = 2; i <= n; i++) {
		if (!sta[i].empty()) {
			memcpy(h, g, sizeof(arr1));
			memcpy(ori, g, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (g[k]) {
						int s1 = vv & sta1[k];
						if (!s1) {
							relax(f[tt[k][vv][2]], g[k]);
						} 
					}
				}
				memcpy(g, f, sizeof(arr1));
				swap(f, g);
			}
			memcpy(f, h, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (h[k]) {
						int s2 = vv & sta2[k];
						if (!s2) {
							relax(f[tt[k][vv][1]], h[k]);
						}
					}
				}
				memcpy(h, f, sizeof(arr1));
				swap(f, h);
			}
			for (int k = 0; k < M; k++) {
				f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < M; i++) {
		relax(ans, f[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

【日常小测】学外语

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞

Code

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

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar()) {
		f = c == '-'? -1: 1;
	}
	for (; '0' <= c && c <= '9'; c = getchar()) {
		ret = ret * 10 + c - '0';
	}
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void AddEdge(int u, int v) {
	in[v]++; deg[v]++; pre[u] = v;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void mrk(int w) {
	vis[w] = 1;
	if (--in[pre[w]] == 0) {
		mrk(pre[w]);
	}
}

inline int cal_node(int w) {
	int ret = R2[deg[w]];
	vector<int> arr;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!in[to[i]]) {
			dep[to[i]] = dep[w] + 1;
			int tmp = cal_node(to[i]);
			arr.push_back(tmp);
			ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
		for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
		ans = (LL)ans * ipw[j - i + 1] % MOD;
	}
	return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
	vector<int> node, arr;
	while (!vis[w]) {
		vis[w] = 1;
		node.push_back(w);
		for (int i = head[w]; i; i = nxt[i]) {
			if (in[to[i]]) {
				w = to[i];
				break;
			}
		}
	}
	for (int i = 0; i < (int)node.size(); i++) {
		dep[node[i]] = 6;
		arr.push_back(cal_node(node[i]));
	}
	int sta = 0, cnt = 1;
	for (int i = 0; i < (int)node.size(); i++) {
		sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
	} 
	int ret = (LL)sta * pw23[n] % MOD;
	for (int i = 1, cur = sta; i < (int)node.size(); i++) {
		cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
		ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
		cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
	}
	ans = (LL)ans * inv[cnt] % MOD;
	return ret;
}

int main() {
	srand(19991216);
	inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
	R1[0] = rand(); R2[0] = rand();
	for (int i = 1; i < N; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		pw23[i] = pw23[i - 1] * 131ll % MOD;
		inv[i] = Pow(i, MOD - 2);
		ipw[i] = Pow(pw[i], MOD - 2);
		R1[i] = rand(); R2[i] = rand();
	}
	
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		memset(in, 0, sizeof(in));
		E = 0; ans = 1;
		
		n = read();
		for (int i = 1; i <= n; i++) {
			AddEdge(i, read());
		}	
		for (int i = 1; i <= n; i++) {
			if (!in[i] && !vis[i]) {
				mrk(i);
			}
		}
		vector<int> arr;
		for (int i = 1; i <= n; i++) {
			if (in[i] && !vis[i]) {
				arr.push_back(cal_cir(i));
			}
		}
		sort(arr.begin(), arr.end());
		for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
			for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
			ans = (LL)ans * ipw[j - i + 1] % MOD;
		}
		ans = ((LL)ans * pw[n] - 1) % MOD;
		printf("%d\n", (ans + MOD) % MOD);
	}
	return 0;
}

【TopCoder SRM713】PowerEquation

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

【Codeforces 797D】Broken BST

相关链接

题目传送门:http://codeforces.com/contest/797/problem/D

解题报告

之前做过类似的题:https://oi.qizy.tech/?p=298
大概就是说,排序之后,每个点的左右子树切换至多发生一次
于是用基排来离散化的话,时间复杂度就是:$O(n)$的

Code

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

const int N = 200009;

int n,rt,is_rt[N],val[N],ch[N][2],TOT[N];
int tot,_hash[N],cnt[N],dep[N],vout;
set<pair<int,int> > id[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void dfs(int w, int f) {
	dep[w] = dep[f] + 1;
	if (ch[w][1]) dfs(ch[w][1], w);
	if (ch[w][0]) dfs(ch[w][0], w);
}

void add(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].insert(make_pair(dep[w], w)); 
	cnt[val[w]]++;
	if (val[w] > sta) add(ch[w][0], sta);
	else add(ch[w][1], sta);
}

void del(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].erase(make_pair(dep[w], w));
	cnt[val[w]]--;
	if (val[w] > sta) del(ch[w][0], sta);
	else del(ch[w][1], sta);
}

int main() {
	n = read();
	for (int i=1,l,r;i<=n;i++) {
		val[i] = read(); _hash[++tot] = val[i];
		if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1;
		if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1;
	}
	for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;}
	dfs(rt, rt);
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++;
	
	add(rt, 1);
	if (!cnt[1]) vout += TOT[1];
	for (int i=2,w;i<=tot;i++) {
		if (id[i].size() > 0) {
			auto tmp = id[i].begin();
			w = tmp->second;
			del(w, i-1);
			add(w, i);
		}
		if (cnt[i] == 0) vout += TOT[i];
	}	
	printf("%d\n",vout);
	return 0;
}

【CodeChef DINING】[January Cook-off 2014] Dining

相关链接

题目传送门:https://www.codechef.com/problems/DINING
官方题解:https://discuss.codechef.com/questions/70332/dining-editorial

解题报告

这题套路啊,神™套路啊!

关键问题是它的概率是乘起来的,不是加起来
于是很多东西都不能用啊!
于是题解说我们可以取对数,因为$\log(a \cdot b) = \log (a) + \log (b)$
于是就变成了加法,于是就可以跑一个费用流了

把乘法换搞成加法,在模意义下还有一种做法,参见:

【BZOJ 3992】[SDOI2015] 序列统计

【BZOJ 4810】[YNOI2017] 由乃的玉米田

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4810
神犇题解:http://blog.csdn.net/qzh_1430586275/article/details/69400458

解题报告

看一看似乎一脸懵逼啊
询问两数相加、相减为特殊值不是只能$FFT$吗?
你这™还带区间限制,那怎么做啊……

但仔细看看值域范围,发现这货只有$10^{10}$
配上$30s$的限制,刚好是$bitset$的数据范围啊!
于是仔细想一想,加法可以直接减法可以直接左移然后$and$起来
至于减法,我们可以记一下负数就可以转化为减法了
至于相乘嘛,我们可以暴力枚举因数!
于是再配上区间的莫队,时间复杂度:$O(n \sqrt{n} + \frac{mc}{64})$

【CodeChef PARITREE】[MARCH16] Parity tree

相关链接

题目传送门:https://www.codechef.com/MARCH16/problems/PARITREE
神犇题解:http://r64.is-programmer.com/posts/197030.html

解题报告

这题大概是PA2014 Kuglarz的升级版
我们发现其给定树上一条路径的奇偶性,实际上可以理解为给定路径上两个端点到根的路径的奇偶性的关系
换一句话来说,这两个的奇偶性定了一个,另一个也就确定了

所以给定$u,v$的奇偶性,就用并查集把这两货连一起
最后假设有$k$个连通块,那答案就是$2^k$
当然我们还需要特判一下无解的情况,在并查集那里多记录一点东西就可以了

【Codeforces 176E】Wizards and Bets

相关链接

题目传送门:http://codeforces.com/problemset/problem/167/E
神犇题解:http://blog.csdn.net/popoqqq/article/details/45046545

吐槽

神™套路题,考试考这个也是简直了
出题人你能不能良心一点 (╯‵□′)╯︵┻━┻

还有一个高一神犇各种瞎搞给做出来了……
牛逼!我就服你!

解题报告

我们可以把给的出发点到目标点配对之后重新标号
于是我们可以看成是一个置换
然后我们考虑在每一个交叉的位置交换那两条路径的目标点
于是这个方案的置换奇偶性一定改变

然后我们考虑如果一套路径方案交叉了奇数次,那么这是一个奇置换,算行列式时系数为$-1$
如果一套路径的方案交叉了偶数次,那么这是一个偶置换,算行列式的时候系数为$1$
这刚好和容斥的系数对上!于是我们算出行列式就相当于用容斥算出了答案

现在回到行列式的定义:$|A|= \sum\limits_{\sigma\in Sn}{{\mathop{\rm sgn}}(\sigma)\prod\limits_{i= 1}^n{{a_{i,\sigma(i)}}}}$
系数已经没有问题了,那么看方案数的统计,我们发现设$f_{i,j}$为$i \to j$的方案数
放到矩阵的对应位置上,刚好又能对上方案数,于是什么都对上了,这题算个行列式就完了

【BZOJ 3028】食物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解:http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊!第一反应:还要写高精?
但想一想似乎物品非常妙妙:

我们强行将其分为四组:{汉堡,可乐} {蜜桃多,土豆片炒肉} {包子,鸡块} {鸡腿,面包}
我们发现每一组都能凑出每一个自然数,且方案唯一
于是问题变为将$n$个球分为$4$组,每组可以为空的方案数

这是插板法的经典问题,于是搞一个组合数就可以了
什么组合数太大?
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$,所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

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

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

【日常小测】cut

题目大意

给定一个$n(n \le 100)$个点的连通图
不同顶点之间有$n^2$个最小割
现在给定这$n^2$个最小割,让你构造一个图使其满足条件

解题报告

据说这是论文题?

因为任意两点间的最小割可以用最小割树来表示
所以我们考虑构造一个树形结构

因为一条路径上的最小割相当于取$min$,所以流量大的不会影响流量小的
所以我们先按边权从大到小排序
如果当前这条边的两个端点已经在一个连通块内,那么暴力判断是否符合要求
如果不在一个块内,那么连一条边

至于为什么这样是对的,因为已经按权值排序了
如果不在一个连通块内,还不连边,那么最终连通这两块的权值一定大于要求的最小割,所以必须立刻连边
至于已经连边了还冲突的话,因为之前的边都是必要的,所以也没有调整的需要,一定是无解的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;
 
int n,tot,head[N],nxt[M],to[M],cost[M],fa[N];
struct Data{
    int u,v,val;
    inline Data() {}
    inline Data(int a, int b, int c):u(a),v(b),val(c) {}
    inline bool operator < (const Data &B) const {
        return val > B.val;
    }
}p[N*N*N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
int cal(int w, int f, int pur, int mn) {
    if (w == pur) return mn;
    for (int i=head[w],tmp;i;i=nxt[i]) {
        if (to[i] != f) {
            tmp = cal(to[i], w, pur, min(mn, cost[i]));
            if (~tmp) return tmp;
        }
    } return -1;
}
 
int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}
 
int main() {
    n = read();
    for (int i=1,v;i<=n;i++) {
        fa[i] = i;
        for (int j=1;j<=n;j++) {
            if (v=read(), i==j) continue;
            p[++tot] = Data(i, j, v);   
        }
    }
    sort(p+1, p+1+tot);
    for (int i=1;i<=tot;i++) {
        int u=p[i].u, v=p[i].v, val=p[i].val;
        if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
        else fa[find(u)] = fa[v], AddEdge(u, v, val);
    }
    cout<<n-1<<endl;
    for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
    return 0;
}

【日常小测】计数

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/03/20170301150237_94661.png

一句话题意

给$n_1$个$A$,$n_2$个$B$,$n_3$个$C$,$n_4$个$D$
问有多少种排列方式,使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$

吐槽

因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ

解题报告

假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2? 因为多出来那一段我们既可以放段首,也可以放段尾

现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串,一定为以下四种情况之一

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次,就是第三种和第四种了,不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$,第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对,然后分成$x$组,允许空集
那么这就是插板法的板题了

于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度:$O(n^2)$

Code

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

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int solve(int a, int b, int c) {
	if (a < b) swap(a, b);
	if (!a && b) return b == c;
	int ret = 0;
	for (int i=a-b,j,k;i<=c;++i) {
		j = i - a + b; k = c - i - j;
		if (j >= 0 && k >= 0 && a >= i + k ) {
			(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
		}
	}
	return ret;
}

int main() {
	PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
	C[0][0] = 1; for (int i=1;i<N;i++) {
		C[0][i] = 1; for (int j=1;j<=i;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	} 
	int a=read(),b=read(),c=read(),d=read();
	if (a + b == 0) f[1] = 1;
	else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
	if (c + d == 0) g[1] = 1;
	else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
	for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3992】[SDOI2015] 序列统计

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3992
Latex题面:http://paste.ubuntu.com/23997878/
数据生成器:http://paste.ubuntu.com/24006205/
神犇题解:http://www.cnblogs.com/gromah/p/4431016.html
NTT相关:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-13

解题报告

这题$O(m^3logn)$的基于矩阵快速幂的算法大家都会吧?
然而只能通过 $60\% $ 的数据 QwQ

然后就需要一点黑科技了
考虑模数这么奇怪,于是可能是用元根来搞一搞
然后我们发现,我们可以用元根的幂次来表示 $0 \sim m – 1$ 的每一个数
于是我们就可以把乘法换成幂次的加法,于是就可以搞NTT了!
于是用NTT来搞生成函数,复杂度:$O(nmlogm)$
然后再套上一开始讲的快速幂,那么就是$O(mlogmlogn)$的复杂度啦!

Code

话说这似乎是第一次撸$NTT$呢!
还有一点小激动啊!
不过这一份代码封装太多了,好慢啊 QwQ

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

const int N = 9000;
const int M = N << 2;
const int MOD = 1004535809;

int l,n,m,x,pos[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, int t, int mod) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%mod)
		if (t & 1) ret = (LL)ret * w % mod;
	return ret;
}

inline int Get_Primitive_Root(int w) {
	vector<int> pri; int cur = w - 1;
	for (int i=2,lim=ceil(sqrt(w));i<=cur&&i<=lim;i++) {
		if (cur % i == 0) {
			pri.push_back(i);
			while (cur % i == 0) cur /= i;
		}
	}
	if (cur > 1) pri.push_back(cur);
	if (pri.empty()) return 2;  
	for (int i=2;;i++) {
		for (int j=pri.size()-1;j>=0;j--) {
			if (Pow(i, w/pri[j], w) == 1) break;
			if (!j) return i;
		}
	}
}

struct Sequence{
	int a[M],POS[M],len;
	inline Sequence() {}
	inline Sequence(int l) {
		memset(a,0,sizeof(a));
		len = l; a[0] = 1;
	}
	inline Sequence(Sequence &B) {
		memcpy(this, &B, sizeof(B));
		len=B.len;
	}
	inline void NTT(int f) {
		static const int G = Get_Primitive_Root(MOD);
		int l = -1; for (int i=len;i;i>>=1) l++;
		if (!POS[1]) {
			for (int i=1;i<len;i++) { 
				POS[i] = POS[i>>1]>>1;
				if (i & 1) POS[i] |= 1 << l-1;
			} 
		}
		for (int i=0;i<len;i++) if (POS[i] > i) 
			swap(a[i], a[POS[i]]);
		for (int seg=2;seg<=len;seg<<=1) {
			int wn = Pow(G, MOD/seg, MOD);
			if (f == -1) wn = Pow(wn, MOD-2, MOD);
			for (int i=0;i<len;i+=seg) {
				for (int k=i,w=1;k<i+seg/2;k++,w=(LL)w*wn%MOD) {
					int tmp = (LL)w * a[k+seg/2] % MOD;
					a[k+seg/2] = ((a[k] - tmp) % MOD + MOD) % MOD;
					a[k] = (a[k] + tmp) % MOD;
				}
			}
		}
		if (f == -1) { 
			for (int i=0,rev=Pow(len,MOD-2,MOD);i<len;i++) 
				a[i] = (LL)a[i] * rev % MOD;
		}
	}
	inline void Multiply(Sequence B) {
		NTT(1); B.NTT(1);
		for (int i=0;i<len;i++)
			a[i] = (LL)a[i] * B.a[i] % MOD;
		NTT(-1); 
		for (int i=m-1;i<len;i++) 
			(a[i-m+1] += a[i]) %= MOD, a[i] = 0;
	} 
	inline void pow(int t) {
		Sequence ret(len),w(*this);
		for (;t;t>>=1,w.Multiply(w)) 
			if (t & 1) ret.Multiply(w);
		memcpy(this, &ret, sizeof(ret));
	}
}arr;

int main() {
	l = read(); m = read();
	x = read() % m; n = read();
	int PRT = Get_Primitive_Root(m);
	for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
	for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0;
	int len = 1; while (len < m) len <<= 1;
	arr.len = len << 1; arr.pow(l); 
	printf("%d\n",(arr.a[pos[x]]+MOD)%MOD);
	return 0;
}