Arrays edu138 div2"/>
D. Counting Arrays edu138 div2
Problem - D - Codeforces
题意是给你一个序列,他的序号是动态的,问你不确定的序列a从1-n数字在1-m里面,问你不确定序列a的个数
分析:容斥+构造
在所有的序列中,不管是什么必须有这样的序列,要想获取不确定的个数
就用全部的个数-确定的个数
确定的个数是什么呢,就是其他任何怎么删都有公约数
所以构造的方法就出来了
不需要每一次都乘i,只需要找到不互质的就可以
所以构造的序列是:
下面就是组合数的知识点了
看代码:
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=998244353;
signed main(){//IOS;int T;T=1;//cin>>T;while(T--){int n,m;cin>>n>>m;int x=1;int now=1;int k=1;int sum=0;for(int i=1;i<=n;i++){x=x*(m%mod)%mod;if(__gcd(i,now)==1){if(k!=0) now*=i;}if(now>m) k=0;k=(k%mod*((m/now)%mod))%mod;sum=(sum+x)%mod;sum=(sum-k+mod)%mod;}cout<<sum<<"\n";}return 0;
}
/*
容斥+构造 */
更多推荐
D. Counting Arrays edu138 div2
发布评论