最近解いた問題たち

CodeForces ABC
Codeforces #239 C Curious Array

解法がわかった時感動した。問題は至ってシンプルで(l,r,k)のクエリがたくさん飛んでくるから配列のlからr番目までに(j-l+k)C(k)(l≦j≦r)を足す。初期値は関係ないので後で足せばOK。
最初nCr=n-1Cr+n-1Cr-1を使って色々変形してみたけど計算量がO(nm)から落ちなくて困ってた。
kCk,k+1Ck…はパスカルの三角形内の部分列で登場する。パスカルの三角形の一部を取ってくると
0C0(=1)……r-lC0
：　　　　　：
：　　　　　：
kCk………r-l+kCk
みたいになっているので
1 0 0 0 … 0 0 -(r-l)C0
0 0 0 ………… -(r-l+1)C0
：　　　　　　　　:
0 ……………… -(r-l+k)Ck
という配列で上から順に横に累積和とって次の段に足してから累積和とるを繰り返せば最下段でkCk…r-l+kCkがO(nk)で得られる。
クエリはm個なのでO(n+m)k)で間に合う。

#define MOD 1000000007ll
ll C[100100][110];
ll a[100100];
ll b[100100][110];
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i=0;i<100100;i++)
	{
		for(int j=0;j<=100;j++)
		{
			if(j==0||i==j)C[i][j]=1;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
		}
	}
	for(int i=1;i<=n;i++)cin >> a[i];
	for(int i=0;i<m;i++)
	{
		int l,r,k;
		scanf("%d %d %d",&l,&r,&k);
		b[l][k+1]++;
		b[l][k+1]%=MOD;
		for(int j=0;j<=k;j++)
		{
			b[r+1][j+1]+=MOD-C[r-l+k-j][k-j];
			b[r+1][j+1]%=MOD;
		}
	}
	for(int i=110;i>0;i--)
	{
		for(int j=1;j<=n;j++)
		{
			b[j][i]+=b[j-1][i];
			b[j][i]%=MOD;
		}
		for(int j=0;j<=n;j++)
		{
			b[j][i-1]+=b[j][i];
			b[j][i-1]%=MOD;
		}
	}
	for(int i=1;i<=n;i++)printf("%I64d%c",(a[i]+b[i][0])%MOD,(i==n)?'\n':' ');
	return 0;
}
Codeforces #240 C Mashmokh and Reverse Operation

マージソートでO(nlogn)で解けるらしいけどBIT使って解いた。
最初に、反転数を分割統治で求める時みたいに2^n個ずつのグループ間の反転数をメモしておく。
各クエリでは、2^q以下でのグループ間での反転数がひっくり返るのですべての組み合わせから引けばいい。ここで、すべての数の組み合わせから同じ数の組みを引いておかないといけないことに注意。
最後に全部足せば答え。
なぜかBITの初期化をmemset(bit,0,sizeof(bit));にするとnが大きい時buildのところで死にます。これで2日くらい無駄にしました。理由わかる方いらっしゃったら教えてください。

int n,m,SIZE;
struct BIT
{
	int bit[(1<<20)+10];
	void clear()
	{
		memset(bit,0,sizeof(bit));
	}
	void add(int i,int x)
	{
		while(i<(SIZE+5))
		{
			bit[i]+=x;
			i+=i&-i;
		}
	}
	int sum(int i)
	{
		int res=0;
		while(i>0)
		{
			res+=bit[i];
			i-=i&-i;
		}
		return res;
	}
};
BIT bit;
int a[(1<<20)+5];
vector<int> vx;
ll p[30],mx[30];
void build(ll l,ll r,int d)
{
	if(d==0)return;
	ll mid=(l+r)/2;
	mx[d]+=(r-mid)*(r-mid);
	for(int i=l;i<mid;i++)bit.add(a[i],1);
	for(int i=mid;i<r;i++)
	{
		p[d]+=(r-mid)-bit.sum(a[i]);
		mx[d]-=bit.sum(a[i])-bit.sum(a[i]-1);
	}
	for(int i=l;i<mid;i++)bit.add(a[i],-1);
	build(l,mid,d-1);
	build(mid,r,d-1);
	return;
}
int main()
{
	scanf("%d",&n);
	SIZE=1<<n;
	for(int i=0;i<SIZE;i++)
	{
		scanf("%d",&a[i]);
		vx.pb(a[i]);
	}
	if(n==0)
	{
		scanf("%d",&m);
		for(int i=0;i<m;i++)printf("0\n");
		return 0;
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	for(int i=0;i<SIZE;i++)a[i]=(lower_bound(vx.begin(),vx.end(),a[i])-vx.begin())+2;
	bit.clear();
	build(0,SIZE,n);
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		int k;
		scanf("%d",&k);
		for(int j=1;j<=k;j++)p[j]=mx[j]-p[j];
		ll ans=0ll;
		for(int j=1;j<=n;j++)ans+=p[j];
		printf("%I64d\n",ans);
	}
	return 0;
}
ABC #007 D 禁止された数字

桁DP。JOIのジグザグ数の簡単verみたいな感じ

ll dp[20][2][2];
ll a,b;
ll ca,cb;
int cnt;
int s[20][2];
ll culc(int digit,bool used,bool flag,int num)
{
	if(digit==-1)return used?1ll:0ll;
	ll &ret=dp[digit][used][flag];
	if(ret!=-1)return ret;
	ret=0;
	for(int i=0;i<=9;i++)
	{
		if(!flag||i<=s[digit][num])ret+=culc(digit-1,(used||i==4||i==9),(flag&&i==s[digit][num]),num);
	}
	return ret;
}
int main()
{
	cin >> a >> b;
	a--;
	memset(dp,-1,sizeof(dp));
	cnt=0;
	while(a>0)
	{
		s[cnt++][0]=a%10;
		a/=10;
	}
	ca=culc(cnt,false,true,0);
	memset(dp,-1,sizeof(dp));
	cnt=0;
	while(b>0)
	{
		s[cnt++][1]=b%10;
		b/=10;
	}
	cb=culc(cnt,false,true,1);
	//cout << cb << ' ' << ca << endl;
	cout << cb-ca << endl;
	return 0;
}

今USACOを埋めてます。気になったのだけ気が向いた時に載せようと思います。