alpharchmage @ 2025-01-10 20:39:18
P10986
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n = 0 , m = 0;
array<int , 100100> fact , fact_inv;
int quick_pow(int x , int y , int p)
{
int res = 1;
while(y)
{
if(y & 1)
{
res *= x;
res %= p;
}
x *= x;
x %= p;
y /= 2;
}
return res;
}
int get_inv(int x)
{
return quick_pow(x , mod - 2 , mod);
}
int C(int n , int m)
{
return fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
fact[0] = 1;
for(int i = 1;i <= n;++ i) fact[i] = fact[i - 1] * i % mod;
for(int i = 0;i <= n;++ i) fact_inv[i] = get_inv(fact[i]);
if(n - 4 * m <= 3)
{
cout << quick_pow(10 , n - 4 * m , mod) * C(n - 4 * m + m , m) % mod << endl;
return 0;
}
else
{
cout << (quick_pow(10 , n - 4 * m , mod) * C(n - 4 * m + m , m) % mod - quick_pow(10 , n - 4 * m - 4 , mod) * C(n - 4 * m - 4 + m + 1 , m + 1) % mod + mod) % mod % mod << endl;
}
return 0;
}
这道题为什么不能用至少(m + 1)个的情况减去至少m个的情况?
by Winston12321_ @ 2025-01-10 21:10:30
因为你的代码算的并不是至少出现m次的字符串数。
例如某个出现了m+2次的串,你理应计算1次,而实际上你计算了
by Winston12321_ @ 2025-01-10 21:13:13
@alpharchmage
by zhouyuhang @ 2025-01-10 21:14:25
实际上这就是二项式反演的意义所在。你以为你求出的“至少
by alpharchmage @ 2025-01-10 21:29:43
@Winston12321_哦,谢谢
by alpharchmage @ 2025-01-10 21:45:27
@zhouyuhang谢谢