题意：一个长度为m的序列，每个数能取1-n的值，有k个限制x,y表示a[x]!=y，求出所有可能的数列的积的和 mod 1000000007的值
分析：很容易能想到，在没有限制的情况下，总和应该是(n*(n+1)/2)^m
推导也很简单，比如我要在n-1的基础上再加上第n个数，这个数在之前数p的基础上还可以取1-n的数
也就是p*1+p*2+...+p*n，也就是p*n*(n+1)/2，也就是说每增加一个数，结果就会乘以n*(n+1)/2
那么剩下就很好办了
用一个map记录是否有重复的限制出现，
用一个vector记录被限制的位数有几个，分别被限制多少
再用一个map防止vector里有重复的位置出现，
最后统计一遍结果，再加一个快速幂即可
代码：
#include<cstdio> #include<map> #include<vector> using namespace std; #define ll long long const int mod=1e9+7; vector<int> q; map<int,ll> num; map<pair<int,int>,bool> mapp; ll pow(ll a,int b) { ll now=a,ans=1ll; while(b) { if(b&1) ans*=now,ans%=mod; b>>=1,now*=now,now%=mod; } return ans; } int main() { int n,m,k,x,y; scanf("%d%d%d",&n,&m,&k); while(k--) { scanf("%d%d",&x,&y); if(!num[x]) q.push_back(x); if(mapp[make_pair(x,y)]) continue; mapp[make_pair(x,y)]=1; num[x]+=(ll)y; } ll n2=(ll)n*(n+1)/2; ll ans=1; for(int i=0;i<q.size();i++) ans*=(n2-num[q[i]])%mod,ans%=mod; printf("%lld",ans*pow(n2%mod,m-q.size())%mod); return 0; }
原文：https://www.cnblogs.com/lin4xu/p/12873480.html