[Noip模拟题]统计方案

题目并不难，想一下就会了，我真的智商持续下降，取模情况下做除法我都没想到逆元。

总之想到逆元就好写了，还是\(meet\ in\ the\ middle\)裸题，数组开不下用\(hash/map\)存一下就好了.

提示：

1、特判\(c==1\)的情况

2、特判\(c>=p\)的情况

#include<cstdio>

#include<map>

int n,p,c,mod=1e9+7,a[40],ans;std::map<int,int>mp;

int mi(int a,int b){int ans=1;while(b){if(b&1)ans=(1ll*ans*a)%p;b>>=1;a=(1ll*a*a)%p;}return ans;}

void dfs(int x,int now){

    if(x>n/2){mp[now]++;return ;}

    dfs(x+1,1ll*now*a[x]%p),dfs(x+1,now);}

void dfs1(int x,int now){

    if(x>n){int b=1ll*c*mi(now,p-2)%p;ans=(ans+mp[b])%mod;return ;}

    dfs1(x+1,1ll*now*a[x]%p),dfs1(x+1,now);}

int main(){

    scanf("%d%d%d",&n,&p,&c);for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    if(c>=p){printf("0\n");return 0;}

    dfs(1,1),dfs1(n/2+1,1);printf("%d\n",c!=1?ans:ans-1);}

巴特西

[Noip模拟题]统计方案

最新文章

热门文章

巴特西

[Noip模拟题]统计方案​

最新文章

热门文章

[Noip模拟题]统计方案