今日解いた問題たち⑦

だんだん難しい問題に当たるようになってきて大変。

156C - Cipher
よく考えたら文字関係無いじゃん…

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[101][2600];
char str[128];
int main(){
	int a;
	int mod=1000000007;
	dp[0][0]=1;
	for(int i=0;i<100;i++){
		for(int j=0;j<2600;j++){
			if(!dp[i][j])continue;
			for(int k=0;k<26;k++)dp[i+1][j+k]=(dp[i+1][j+k]+dp[i][j])%mod;
		}
	}
	scanf("%d",&a);
	while(a--){
		scanf("%s",str);
		int n=strlen(str);
		int v=0;
		for(int i=0;i<n;i++)v+=str[i]-'a';
		printf("%d\n",(dp[n][v]+1000000006)%mod);
	}
}

239C - Not Wool Sequences
i番目の数を置くときに、1～i-1,2～i-1,3～i-1…番目たちのxorと重複しなければよく、
これらの数たちは絶対に重複しない(重複するとその差がxorが0になる)ので、(2^m-1)Pnを求めるだけ。
気づきゲーだが、Div2Cにしてはかなり難しいと思う。

#include<stdio.h>
int main(){
	int mod=1000000009;
	int a,b;
	scanf("%d%d",&a,&b);
	long long ret=1;
	int now=1;
	for(int i=0;i<b;i++){
		now=now*2%mod;
	}
	now=(now+1000000008)%mod;
	for(int i=0;i<a;i++){
		ret=ret*now%mod;
		now=(now+1000000008)%mod;
	}
	printf("%d\n",(int)ret);
}