Inclusion-exclusion

  The principle of inclusion-exclusion provides us with a technique for solving problems like couting. For example, how many numbers not exceeding $1000$ are divisible by $7$ or $11$?

solution: Let $A$ be the set of positive numbers which are not exceeding $1000$ and divisible by 7, and let $B$ be the set of positive numbers which are not exceeding $1000$ and divisible by 11. Define $\vert A\vert$ to be the number of elements in $A$, we have

$$ \begin{equation} \begin{aligned} \vert A\cup B\vert&=\vert A\vert+\vert B\vert-\vert A\cap B\vert \\ &=\lfloor \frac{1000}{7}\rfloor+\lfloor \frac{1000}{11}\rfloor-\lfloor \frac{1000}{7\times11}\rfloor \\ &=220. \end{aligned} \end{equation} $$

  Thus, the answer should be $220$.

  In fact, there’s a theorem.

Theorem(The principle of inclusion-exclusion) Let $A_1, A_2, \dots, A_n$ be finite sets. Then

$$ \begin{equation} \begin{aligned} \vert\bigcup_{i=1}^{n}A_i\vert&=\sum_{1\le i\le n}\vert A_i\vert -\sum_{1\le i<j\le n}\vert A_i\cap A_j\vert\\ &+\sum_{1\le i<j<k\le n}\vert A_i\cap A_j\cap A_k\vert-\cdots+(-1)^{n}\vert \bigcap_{i=1}^{n}A_i\vert. \end{aligned} \end{equation} $$

Sample: [codeforces 1228E]Another filling the grid

  Let $S_{i,j}$ be a collection of situations with i rows and j colomns do not satisfy the condition, that is, for every grid in this i rows or j colomns, its value should be greater than 1. We could use a fomular to calculate this $\vert S_{i,j}\vert$:

$$ \vert S_{i,j}\vert=C_{n}^{i}\times C_{n}^{j}\times (k-1)^{n(i+j)-ij}\times (k-1)^{n^2-n(i+j)+ij} $$

  Now we want to obtain $\vert \bigcup_{i,j}S_{i,j}\vert$. By observation, we know that $S_{i,j}=S_{i,0}\cap S_{0,j}$, $S_{i,0}\subset S_{j,0}$ if $j<i$, $S_{0,i}\subset S_{0,j}$ if $j<i$ and $S_{i,j}\cap S_{k,l}=S_{i,0}\cap S_{0,j}\cap S_{k,0}\cap S_{0,l}=S_{max(i,k),max(j,l)}$. In additional, given the theorem, we can figure out that every $S_{i,j}$ contributes to $\vert \bigcup_{i,j}S_{i,j}\vert$ with the coefficient $(-1)^{i+j}$.

  Then apply the theorem, we get

$$ \vert \bigcup_{i,j}S_{i,j}\vert=\sum_{i=0}^{n}\sum_{j=0}^{n}(-1)^{i+j}\times C_{n}^{i}\times C_{n}^{j}\times (k-1)^{n(i+j)-ij}\times (k-1)^{n^2-n(i+j)+ij}, $$

note that $\vert S_{0,0}\vert$, by fomular, equals to $k^n$, which is the total number of ways to fill the grid. And therefore the answer would be this $\vert \bigcup_{i,j}S_{i,j}\vert$. The time complexity of the algorithm should be $O(n^{2}logn)$.

  The answer is required to take mod. The law of addition and multiplication under mod operation is well known. But this time we used the formular $C_{n}^{i}=\frac{n!}{(n-i)!i!}$ to calculate combination, hence the inverse of an element is needed. There is a trick to find the inverse of an element: applying Fermat’s little theorem,

$$ a^{p-1}\equiv1(mod \hspace{0.2cm}p) $$

where $p$ is prime, $(a,p)=1$. Thus,

$$ a\times a^{p-2}\equiv 1(mod \hspace{0.2cm}p) $$

i.e., $a^{p-2}$ is the inverse of $a$.

my code:

#include<bits/stdc++.h>
const int mod =1e9+7;
typedef long long ll;
int n,k;
namespace NT{
	ll tm(ll x){
		return (x%mod+mod)%mod;
	}
	ll pw(ll x,ll y){
		ll res=1,bas=x;
		while(y){
			if(y&1){
				res=tm(res*bas);
			}
			bas=tm(bas*bas);
			y>>=1;
		}
		return res;
	}
	ll ginv(ll x){
		return pw(x,mod-2);
	}
	ll fac[255],Com[255];
	ll Ans;
	void getfac(){
		fac[0]=1;
		ll F=1;
		for(int i=1;i<=n;++i){
			F=tm(F*i);
			fac[i]=F;
		}
	}
	void getCom(){
		for(int i=0;i<=n;++i){
			ll cur=tm(fac[n]*ginv(fac[n-i]));
			cur=tm(cur*ginv(fac[i]));
			Com[i]=cur;
//			printf("%lld ",Com[i]);
		}
	}
	void getAns(){
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j){
				ll coe=1;
				if((i+j+1)%2==0)coe=-1;
				ll sij=tm(Com[i]*Com[j]);
				ll k_1p=pw(k-1,n*(i+j)-i*j);
				ll kp=pw(k,n*n+i*j-n*(i+j));
				sij=tm(sij*k_1p);
				sij=tm(sij*kp);
				Ans=tm(Ans+coe*sij);
//				printf("%lld ",sij*coe);
			}
		}
	}
	void work(){
		getfac();
		getCom();
		getAns();
		printf("%lld",Ans);
	}
}
using namespace NT;
int main(){
	scanf("%d%d",&n,&k);
	work();
	return 0;
}
 
// printf("%lld",);