【 2017 ACM-ICPC 亚洲区(西安赛区)网络赛】 F. Trig Function
程序员文章站
2022-06-04 12:25:10
...
f(cos(x))=cos(n∗x)
holds for all x.
Given two integers n and m, you need to calculate the coefficient of x^m in f(x), modulo 998244353.
Input Format
Multiple test cases (no more than 100).
Each test case contains one line consisting of two integers n and m.
1≤n≤10^9,0≤m≤10^4.
Output Format
Output the answer in a single line for each test case.
样例输入
2 0
2 1
2 2
样例输出
998244352
0
2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
#include <cstring>
#include <ctime>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const long long M = 998244353;
ll powmod(ll a, ll b, ll p)
{
ll res = 1;
while (b != 0)
{
if (b & 1)
{
res = (res * a) % p;
}
a = (a * a) % p;
b >>= 1;
}
return res;
}
ll comb(ll a, ll b, ll p)
{
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)) % p;
cb = (cb * (b - i)) % p;
}
ans = (ca * powmod(cb, p - 2, p)) % p;
return ans;
}
ll Lucas(int n, int m, int p)
{
ll ans = 1;
while (n && m && ans)
{
ans = (ans * comb(n % p, m % p, p)) % p;
n /= p;
m /= p;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
ll n, m;
while (cin >> n >> m)
{
if (n - m < 0 || (n - m) % 2 != 0)
{
cout << 0 << endl;
continue;
}
ll k = (n - m) / 2;
ll ans = 0;
if (k % 2 == 0)
{
ans = (n * Lucas(n - k, k, M) % M * powmod(2, m, M) % M * powmod(n + m, M - 2, M) ) % M;
cout << ans << endl;
}
else
{
ans = (-n * Lucas(n - k, k, M) % M * powmod(2, m, M) % M * powmod(n + m, M - 2, M)) % M;
cout << (ans + M) % M << endl;
}
}
return 0;
}
上一篇: 樱桃怎么清洗最干净
下一篇: 煮猪头肉放什么料香小秘密