2017 ACM-ICPC 亚洲区（西安赛区）网络赛 F Trig Function(数论，组合数)

你的名字 2022-06-08 06:00 166阅读 0赞

**Trig Function**

*f*(*c**o**s*(*x*))=*c**o**s*(*n*∗*x*) holds for all x*x*.

Given two integers n*n* and m*m*, you need to calculate the coefficient of x^m*x**m* in f(x)*f*(*x*), modulo 998244353998244353.

### Input Format ###

Multiple test cases (no more than 100100).

Each test case contains one line consisting of two integers n*n* and m*m*.

1 \\le n \\le 10^9,0 \\le m \\le 10 ^ 41≤*n*≤109,0≤*m*≤104.

### Output Format ###

Output the answer in a single line for each test case.

#### 样例输入 ####

2 0
    2 1
    2 2

#### 样例输出 ####

998244352
    0
    2

题意：把题目中给你的函数化成f(x)。然后求x^m的系数。

思路：首先第一步，如题意所说，把题目中的函数化成f(x)形式的函数，这里就需要一些数学知识了，首先我们根据n倍角公式把cos(nx)给转化一下，n倍角公式如下图。因为是余弦所以用上面的一个。

![Center][]

然后(sinx)^2i可以转化成(1-(cosx)^2)^i，这样整个式子里就只有cosx了。又因为题目里的函数前面恰好是f(cosx)，所以我们只需要把 所 有的cosx全部替换成x，这样就成功把式子转化成f(x)了。最终式子如下。

![Center 1][]

那么接下来就是如何根据这个式子求x^m的系数了。首先我们可以发现，这个式子中对x系数有影响的只有x^(n-2i)和(1-x^2)^i，这两个式子都有一个很大的特点，当n为奇数的时候，第一个式子只能提供x的奇数次幂，当n为偶数的时候，第一个式子只能提供x的偶数次幂，而第二个式子则无论何时都只能提供x的偶数次幂，这样我们就可以得到一个结论，当n为奇数时，一切偶次幂的x的系数全为0，当n为偶数时，一切奇次幂的x的系数全为0。

然后我们再考虑n和m同奇同偶的情况，虽然题目里n的范围是1e9，很大，但是m的范围只有1e4，我们完全可以找出这个式子中的每一个x^m的项，然后把它们的系数求和就是答案。我们可以先找出一个满足n-2i=m的i，此时第一个式子对x次幂的贡献就是m了，那么第二个式子只需要贡献常数即可，那么(-1)^i\*C(n,2i)\*第二个式子常数项系数就是我们算出第一个x^m次幂的系数，加入到ans里，接下来我们将i++，这时第一个式子对x次幂的贡献是m-2，那么这时第二个式子就需要贡献x^2，这样才能保证相乘后依然是x^m，所以(-1)^i\*C(n,2i)\*第二个式子x^2的系数是我们算出的第二个x^m次幂的系数，加入到ans里，依此类推，一直循环到i的上限，最后的ans就是最终答案。

第二个式子展开其实就是杨辉三角，x^k的系数用组合数去求即可。

还有一点要注意的是求组合数的时候不要每一个组合数都从头求一遍，第一个组合数是C(n,2i)，i每次+1，那么我们可以根据上一个组合数推出下一个组合数的值，第二个式子里的组合数也是如此，如果每个都重算一遍的话会超时。

思路大体上已经讲的很清楚了，比赛时代码写得比较丑，主要看思路。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 10007;
    const int MOD = 998244353;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL quick_mod(LL a, LL b, LL c)
    {
    	LL ans = 1;
    	while (b)
    	{
    		if (b % 2 == 1)
    			ans = (ans*a) % c;
    		b /= 2;
    		a = (a*a) % c;
    	}
    	return ans;
    }
    
    LL Comb(LL a, LL b) {
    	if (a < b)   return 0;
    	if (a == b)  return 1;
    	if (b > a - b)   b = a - b;
    	LL ans = 1, ca = 1, cb = 1;
    	for (LL i = 0; i < b; ++i) {
    		ca = (ca * (a - i)) % MOD;
    		cb = (cb * (b - i)) % MOD;
    	}
    	ans = (ca*quick_mod(cb, MOD - 2, MOD)) % MOD;
    	return ans;
    }
    
    LL m;
    
    int main()
    {
    	LL ans, ss;
    	LL v1, v2, n1, m1, n2, m2;
    	while (scanf("%lld%lld", &n1, &m) != EOF)
    	{
    		ans = 0;
    		n2 = (n1 - m) / 2;
    		ss = 0;
    		v1 = Comb(n1, 2 * n2);
    		v2 = Comb(n2, 0);
    		if (n1 % 2 == 1 && m % 2 == 0 || n1 % 2 == 0 && m % 2 == 1)
    		{
    			printf("0\n");
    			continue;
    		}
    		for (LL i = m; i >= 0; i -= 2, ss++)
    		{
    			n2 = (n1 - i) / 2;//从这开始代码写得很丑，大家看我前面写的思路吧
    			m1 = 2 * n2;
    			m2 = n2 - ss;
    			ans = (ans + (v1*v2 % MOD + MOD) % MOD*((n2 + ss) % 2 == 0 ? 1 : -1) % MOD + MOD) % MOD;
    			v1 = (v1*(n1 - m1) % MOD + MOD) % MOD;
    			v1 = v1*quick_mod(m1 + 1, MOD - 2, MOD) % MOD;
    			m1++;
    			v1 = (v1*(n1 - m1) % MOD + MOD) % MOD;
    			v1 = v1*quick_mod(m1 + 1, MOD - 2, MOD) % MOD;
    			v2 = (v2*(n2 + 1) % MOD + MOD) % MOD;
    			v2 = v2*quick_mod(n2 - m2 + 1, MOD - 2, MOD) % MOD;
    		}
    		printf("%lld\n", ans);
    	}
    }

[Center]: /images/20220608/4786f78854d44ef6a5403dc75251c720.png
[Center 1]: /images/20220608/ab9e713df2934b43abacb4ab21221373.png