2017 ACM-ICPC 亚洲区（西安赛区）网络赛 F. Trig Function （切比雪夫多项式）
题意：
思路：手算了几项，然后把n为6的那一行输到OEIS，就搜到了切比雪夫多项式。
切比雪夫多项式前几项为:
|
The triangle a(n,m) begins: n\m 0 1 2 3 4 5 6 7 8 9 10 0: 1 1: 0 1 2: -1 0 2 3: 0 -3 0 4 4: 1 0 -8 0 8 5: 0 5 0 -20 0 16 6: -1 0 18 0 -48 0 32 7: 0 -7 0 56 0 -112 0 64 8: 1 0 -32 0 160 0 -256 0 128 9: 0 9 0 -120 0 432 0 -576 0 256 10: -1 0 50 0 -400 0 1120 0 -1280 0 512 |
然后百度第一类切比雪夫多项式是这个公式：
注意"!!"不是阶乘的阶乘，而是不超过n且与n具有相同奇偶性的所有正整数连乘积。
n分类讨论下,当n为偶数时m=2*k, n为奇数时m=2*k-1
还有注意下"!!"的约分,可能下面的比上面的大
代码：
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5+5;
- const int mod = 998244353;
- ll fac[maxn] = {1};
- ll n, m;
- void init()
- {
- for(int i = 1; i < maxn; i++)
- fac[i] = fac[i-1]*i%mod;
- }
- ll qmod(ll x, int q)
- {
- ll res = 1;
- while(q)
- {
- if(q%2) res = res*x%mod;
- x = x*x%mod;
- q /= 2;
- }
- return res;
- }
- int main(void)
- {
- init();
- while(~scanf("%lld%lld", &n, &m))
- {
- if(m > n) puts("0");
- else if(n%2 && m%2 == 0) puts("0");
- else if(n%2 == 0 && m%2) puts("0");
- else
- {
- ll fz = n%mod;
- if(m >= 1)
- {
- for(int i = n-m+1; i <= n+m-1; i++)
- {
- if(i%2 == (n+m-2)%2)
- {
- fz = fz*i%mod;
- }
- }
- ll tmp = fz*qmod(fac[m], mod-2)%mod;
- if((n-m)/2%2) tmp = -tmp;
- printf("%lld\n", (tmp+mod)%mod);
- }
- else
- {
- ll t = 1;
- for(int i = n+m-1; i <= n-m; i++)
- {
- if(i%2 == (n+m-2)%2)
- t = t*i%mod;
- }
- ll tmp = fz*qmod(fac[m], mod-2)%mod*qmod(t, mod-2)%mod;
- if((n-m)/2%2) tmp = -tmp;
- printf("%lld\n", (tmp+mod)%mod);
- }
- }
- }
- return 0;
- }
|
The triangle a(n,m) begins: n\m 0 1 2 3 4 5 6 7 8 9 10 0: 1 1: 0 1 2: -1 0 2 3: 0 -3 0 4 4: 1 0 -8 0 8 5: 0 5 0 -20 0 16 6: -1 0 18 0 -48 0 32 7: 0 -7 0 56 0 -112 0 64 8: 1 0 -32 0 160 0 -256 0 128 9: 0 9 0 -120 0 432 0 -576 0 256 10: -1 0 50 0 -400 0 1120 0 -1280 0 512 |